Haskellでの関数のルーピング

Question

私はちょうどこれに困惑しています、それは私が書く方法を理解することができないハスケルループソートのものです。基本的には、私は3つの関数split,リフルとシャッフルを定義しました。

riffle [1,2,3] [4,5,6] = [1,4,2,5,3,6] 

をシャッフルの分割量とrifflingを反復することである。

split :: [a] -> ([a],[a]) 
split xs = splitAt (length xs `div` 2) xs 

riffle :: [a] -> [a] -> [a] 
riffle xs [] = xs 
riffle [] ys = ys 
riffle (x:xs) (y:ys) = x:y:riffle xs ys 

shuffle :: Int -> [a] -> [a] 
shuffle 0 xs = xs 
shuffle n xs = shuffle (n-1) (riffle a b) 
    where (a, b) = split xs 

は、基本的にはちょうど半分にリストを分割例えばので、リフルは、二つのリスト「インターレース」になっている分割しましたリストアイテム。今度は関数を定義する必要があります。は、元のリストを再度取得するためにシャッフルの繰り返し回数を出力します。機能は、次のように定義されます

repeats :: [Int] -> Int 

私はちょうど私がそれはリスト内包とは何かを持っていると思う...あなたがシャッフルをループを実行することができますどのようにとこだわってますが、私は何かを得ることができませんでした。私はラムダ式をまだ試していないが、それは必要ではないと思う。ちなみに、シャッフルは偶数項目のリストで行う必要があります。何か案は？

Answer 1

これを解決する1つの方法は、怠惰を利用し、iterateを使用して入力の反復シャッフルの無限リストを生成することです。

> iterate (uncurry riffle . split) "ABCDEF" 
["ABCDEF","ADBECF","AEDCBF","ACEBDF","ABCDEF","ADBECF","AEDCBF","ACEBDF", ...] 

リストの最初の要素はオリジナルのものであるので、我々はtailで、元異なっていたものを取得するためにtakeWhileを使用することをドロップします。

> takeWhile (/= "ABCDEF") . tail $ iterate (uncurry riffle . split) "ABCDEF" 
["ADBECF","AEDCBF","ACEBDF"] 

は今、あなただけのそのリストのlengthを取り、シャッフルの必要数を取得するために1を追加する必要があります。

Answer 2

多くの場合、「ループ」ではなく無限のリストを使用できます。これはその一つです。

プレリュード機能を繰り返し使用すると、開始リストに「反復シャッフル」を適用した場合、あなたは進歩的なシャッフルを取得するので、（メモリから）ので、値に

iterate f x = [x, f x, f (f x), f (f (f x)) ....] 

を関数を適用する「反復」。次に、takeWhileを使用して、開始点と等しいリスト内の最初の項目を見つけ、次に「長さ」を見つけてどれくらいの長さであるか調べます。

Answer 3

ハスケルでは、反復処理はループ処理ではなく再帰処理を使用して最も一般的に表現されます。

これは、反復処理の方法を示す内部関数を使用して、しばしば適切な引数を持つ内部関数を呼び出すことによって行われます。

おそらく次のコードでギャップを埋めることができますか？

repeats xs = iter 1 (...) where 
    iter n ys = if ys == xs 
     then n 
     else iter (...) (...) 

別のアプローチを繰り返し、最初の引数に関数を適用する高階関数iterateを使用して、Haskellの怠惰を活用し、無限のリストでそれを行うことです：iterateものの

repeats xs = (...) $ takeWhile (...) $ iterate (shuffle 1) (...) 

無限のリストを返すので、私たちはそれの有限部分のみを使用するので、無限ループにはなりません。