haskell - Haskellでの無限リストの構築

Question

目的の無限リストには2つのものがあります。最初の要素です。

x :: A

そして次の要素を生成する関数

f :: [A] -> A

無限のリストを作成するための最良の（最も慣用的な？最速の？）方法は何ですか？つまり

xs = x : f [x] : f [x, f [x]] : f [x, f [x], f [x, f [x]]] : ...

Answer 1

必要な関数は次のように実装できます。

constructInf :: ([a] -> a) -> a -> [a]
constructInf f x = xs
  where xs = x:map f (tail $ inits xs)

のパフォーマンスはconsrtuctInf、その引数関数のパフォーマンスに依存しますf。fO（N）時間がかかると仮定すると、 constructInfO（M * N）時間がかかります。ここで、Mは、constructInf検査する結果からの要素の数です。

Answer 2

あなたが欲しいiterate。

take 10 $ iterate (+1) 0

= [0,1,2,3,4,5,6,7,8,9]

これまでのところリスト全体が必要で、それを逆にしてもかまわない場合は、次のようにすることができます。

mkl f x0 = x0 : unfoldr (\xs -> let x = f xs in Just (x, x:xs)) [x0]

これまでのところリスト全体が必要で、順番にリストが必要な場合、それは本当に非効率的ですが、これを行うことができます。

mkl' f x0 = x0 : unfoldr (\xs -> let x = f xs in Just (x, xs ++ [x])) [x0]

しかし、最後の要素だけでなく、リスト全体が必要な理由はわかりません。