unfoldrが分かった!!! #Haskell

unfoldrが今まで全く分からなかったけど, やっとの事で理解できたので説明します.

unfoldrとは

これの説明が割と面倒なんですが, ざっくり言えば"もろもろの条件からリストを生成しますよ"的なやつです.
多分下手に文字で説明するより実際のコードを見た方が早いです.

今回はこの記事で作った選択ソートを用いて説明したいと思います.

選択ソートとは

一応選択ソートの説明をしておきます.

選択ソートは,

1. 未整列リストの最小値を整列済みリストの最後尾に移動させる
2. 未整列リストに対して1の処理を再帰的に行う

というソートアルゴリズムです.

実際にやってみた

ではまずお馴染みの, 関数の型調べから始めたいと思います.
GHCiを開いてunfoldrの型を調べてみます.

> import Data.List
> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

はい, だいぶ面倒くさそうな型が出てきましたね.
順番に見ていきましょう.

まずは第1引数の b -> Maybe (a, b) です.
これは, 何らかの型 b を引数に取り, Maybe (a, b) というタプルを返す関数です.

次に第2引数.
これは簡単ですね. 第1引数に出てきた b と同じ型です.

最後に返す型です.
第1引数に出てきた a と同じ型のリスト, [a] です.

纏めましょう.
unfoldr関数は, "何らかの型 b を引数に取り, Maybe (a, b) というタプルを返す関数"と, "b"を引数に取り, "a のリスト"を返す関数です.

そしてunfoldr関数が実際に行う処理ですが, 第1引数の関数が Nothing を返すまで繰り返し, Maybe (a, b) の a を順に連結したリストを返します.

今回はunfoldrを用いた選択ソートを作る為に, この実装を

1. 未整列リストを, 最小値と最小値を除いたリストに分ける関数を作る
2. 1の関数を用いてunfoldrで整列済みリストを生成

という流れで処理を行うように実装したいと思います.

まずはリストを分ける関数です

separateMinimum :: Ord a => [a] -> Maybe (a, [a])
separateMinimum []   = Nothing
separateMinimum list = Just (x, xs)
    where
        x = minimum list
        xs = delete x list

以上のように定義することができます.

これで, 後はunfoldr関数にこの関数を渡すだけです.

selectionSort :: Ord a => [a] -> [a]
selectionSort = unfoldr separateMinimum

はい, これで完成です.

専用の独特な型の関数が必要だという点が少しとっつきにくくなっている要因なのではないかと思います.
やっぱり型を見る事は大事ですね!

おまけ

10進数を2進数に変換するやつ作ってみました.

IntToBin.hs

import Data.List

intToBin :: Int -> Int
intToBin = (read . concat . map show) . reverse . unfoldr (\x ->
        if x == 0
                then Nothing
                else Just (mod x 2, div x 2))