2

を使用せずに Haskell で左から右にリストを作成する方法はあります++か?

cons一定時間の操作であり、コードを効率的に保ちたい. Haskell の怠惰さを利用してこのようなことを行う一般的な方法があるように感じますが、思いつきません。

現在、コラッツ シーケンスを作成する関数を作成していますが、間違った方向にリストを作成しています。

module CollatzSequence where

collatz :: (Integral a) => a -> [a] -> [a];
collatz n l
  | n <= 0    = error "Enter a starting number > 0"
collatz n []  = collatz n [n]
collatz n l@(x:_)
  | x == 1    = l
  | even x    = collatz n ((div x 2):l)
  | otherwise = collatz n ((x*3 + 1):l)

GHCiでは:

*CollatzSequence> collatz 13 []
[1,2,4,8,16,5,10,20,40,13]
4

2 に答える 2

10

怠惰を利用する方法は確かにあります。Haskellでは、遅延データ コンストラクター内で安全に再帰呼び出しを行うことができ、スタック オーバーフローや発散のリスクはありません。コンストラクター内に再帰呼び出しを配置すると、アキュムレーターが不要になり、リスト内の要素の順序も、それらが計算される順序に対応します。

collatz :: Integer -> [Integer]
collatz n | n <= 1 = []
collatz n = n : collatz next where
    next = if even n then div n 2 else n * 3 + 1

たとえば、式head $ collatz 10は に評価され、 head (10 : <thunk>)which は に評価さ10れ、末尾のサンクは評価されないままになります。もう 1 つの利点は、リストの反復処理中にリスト ノードをガベージ コレクションできることです。foldl' (+) 0 (collatz n)訪問したノードはプログラムの残りの部分から参照されなくなり、解放できるため、定数空間で実行されます。これは元の関数には当てはまりません。末尾再帰であるため、リスト全体が計算されるまで部分的な結果を提供できないためです。

于 2014-05-20T19:51:57.110 に答える