7

私はフィボナッチ数の無限のリストを作成する次のコードを書きました：

fibs = 1:1:fib 1 1
  where fib a b = a+b:fib b (a+b)

上記のコードは、再帰を使用してfoldl、またはfoldr再帰を回避するために記述できますか？

4

4 に答える 4

15

および関数foldlはfoldrリストコンシューマーです。svenningssonの答えが正しく指摘しているように、はの共再帰構造をキャプチャするのに適しunfoldrたリストプロデューサーです。fibs

ただし、foldlとfoldrはリターンタイプ、つまりリストを消費することによって生成するものがポリモーフィックであることを考えると、あるリストを消費して別のリストを生成するために使用できるかどうかを尋ねるのは合理的です。これらの作成されたリストのいずれかが無限である可能性がありますか？

の定義を見てfoldl

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a []        = a
foldl f a (b : bs)  = foldl f (f a b) bs

foldl何かを生成するためには、それが消費するリストは有限でなければならないことがわかります。したがって、foldl f aが無限の出力を生成する場合、それはaが無限であるか、f場合によっては無限のリスト生成を実行するためです。

それは別の話ですfoldr

foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f a []        = a
foldr f a (b : bs)  = f b (foldr f a bs)

これは、入力から消費されるfたびに出力を生成する可能性のある怠惰な可能性を認めています。bのような操作

map g = foldr (\ b gbs -> g b : gbs) []   -- golfers prefer ((:) . g)
stutter = foldr (\ x xxs -> x : x : xxs) []

入力ごとに少しの出力を生成し、無限の入力から無限の出力を提供します。

foldrしたがって、生意気な人は、無限の再帰を無限のリストで非再帰として表現できます。例えば、

foldr (\ _ fibs -> 1 : 1 : zipWith (+) fibs (tail fibs)) undefined [1..]

（編集：または、そのことについては

foldr (\_ fib a b -> a : fib b (a + b)) undefined [1..] 1 1

これは、質問の定義に近いものです。）

この観察結果は真実ですが、健全なプログラミングスタイルを示すものではありません。

于 2012-09-06T11:37:28.267 に答える
11

で無限のリストを作成できるかどうかはわかりませんfoldl。を使用してこの問題を解決できる可能性がfoldrありますが、折りたたむために別のリストを作成する必要があります。そのリストは何でしょうか？他のリストから生成されたことを示唆するフィボナッチ数には何もありません。

代わりに必要なのは、を使用することunfoldrです。foldlおよびの場合のように、リストを使用する代わりに、リストを作成するために使用できますfoldr。unfoldrフィボナッチ数の無限のリストを生成するために使用する方法は次のとおりです。

fib = unfoldr (\(a,b) -> Just (a,(b,a+b))) (1,1)

基本パッケージunfoldrのモジュールにあります。Data.List

于 2012-09-06T10:47:57.263 に答える
3

明示的な再帰を回避する1つの方法は、を使用fixして再帰を固定小数点として表現することです。

import Data.Function (fix)

fibs = fix $ \l -> [1,1] ++ zipWith (+) l (tail l)

またはポイントフリースタイルで

import Data.Function (fix)
import Control.Monad.Instances

fibs = fix $ ([1,1] ++) . (zipWith (+) =<< tail)
于 2012-09-07T05:47:38.513 に答える
1

zipWithあなたはあなたの定義を書くために使うことができます

fibonacci = 1:1:zipWith (+) fibonacci (tail fibonacci)

編集：わかりました。foldlまたはfoldrを使用して無限のリストを作成できるとは思いません。単純な想像できる意味ではありません。foldlの簡単な定義を見ると

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldlは、リスト全体を使い果たすまで戻ることはありません。だから簡単な例のような

g = foldl f [] [1..]
 where 
  f xs a = xs ++ [a]

> take 10 g

でも動作せず、永久にループします。

于 2012-09-06T10:49:25.573 に答える