iterateを使ってみる。

iterate を検索しましら、「iterateでバブルソート 」があったので自分でもバブルソートをしてみようと思いましたら、ちょっと躓きました。

まず、自分でやってみます。

toRightEdge [x]                  = [x]
toRightEdge (x:y:ls) | x > y     = y:toRightEdge (x:ls)
                     | otherwise = x:toRightEdge (y:ls)

bubbleSort [] = []
bubbleSort ls =  x : bubbleSort xs
   where
     (x:xs) = reverse $ toRightEdge ls

リストを受け取り一番大きい値が右端に行く関数 toRightEdge。

 *Main> toRightEdge [1,5,9,4,3,7,2] --=> [1,5,4,3,7,2,9]

次に、最大値は決定したので、残りのリストを繰り返し適用させます。

 Main> bubbleSort [1,5,9,4,3,7,2] --> [9,7,5,4,3,2,1]

「iterateでバブルソート 」のはこれ。

>  :t iterate (+1) 1        -- > iterate (+1) 1 :: Num a => [a]
>  take 10 $ iterate (+1) 1 -- > [1,2,3,4,5,6,7,8,9,10]

module BSort (bsort) where

bsort[]=[]
bsort xs=
  iterate swapPass xs!!(length xs-1)

swapPass[x]=[x]
swapPass (x:y:zs)
  | x>y=y:swapPass(x:zs)
  | otherwise=x:swapPass(y:zs)
                  
main=print $ bsort [1,5,4,3,2]

 Main> let xs= [1,5,9,4,3,7,2]
 Main> iterate swapPass xs!!(length xs-1) --=> [1,2,3,4,5,7,9]

 -- xs!!(length xs-1) の値は２・・・？
 -- ここで？？？
 Main> xs!!(length xs-1) --=> 2

 -- 説明を良く読むと無限リストを作成し、その (length xs-1) 番目のリストを取得するようです。
 -- () で分かりやすくすると。
 Main> (iterate swapPass xs) !! (length xs-1) --=> [1,2,3,4,5,7,9]

 -- 別の書き方をすれば以下のようになります。
 Main> take (length xs-1) (iterate swapPass xs) 
 --=> [[1,5,9,4,3,7,2],[1,5,4,3,7,2,9],[1,4,3,5,2,7,9],[1,3,4,2,5,7,9],[1,3,2,4,5,7,9],[1,2,3,4,5,7,9]]

 Main> last $ take (length xs-1) (iterate swapPass xs) --=> [1,2,3,4,5,7,9]

• 先の例ではtoRightEdgeを実行する度に、次にtoRightEdgeへ渡すリストを短くしていますが後の例では富豪的に全部渡しています。
• 先の例では最大値が決定する度に結果のリストがひとつずつ構築されますが、後の例では1回並べ変えたリスト、2回並べ変えたリストと無限にリストが構築され、そこから「ここなら完璧に整列しているはず」という位置のリストを取得します。これも富豪的です。