3

Programming in Haskell で、Graham Hutton はリストの展開を次のように定義しています。

unfold :: (b -> Bool ) -> (b -> a) -> (b -> b) -> b -> [a]
unfold p h t x | p x = []
| otherwise = h x : unfold p h t (t x)

関数を定義する

• listUnfold :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]

これは上記のものと似ていますが、実装に unfoldr を使用し、再帰的ではありません。

上記の質問を解決するためにしばらく試してみましたが、まだ解決できます (Haskell および関数型プログラミング全般ではかなり新しいものです)。

私の試み：

listUnfold :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]
listUnfold f h t x 
    | f x == True   = []
    | otherwise     = h x : 
        listUnfoldr (\x -> if f x then Nothing else Just ((h x), (t x))) x

英語でf xは、true の場合、空のリストを返します。それ以外の場合はh x、先頭として使用し、unfoldr の結果を末尾として追加します。Unfoldr は、先頭および末尾として(x:xs)自身を再帰する必要があるリストを取ります。xxs

p/s: 私はおそらくこれを非常に間違ってやっています。

4

2 に答える 2

6

あなたはほとんどそれを手に入れました！元の関数は、p(「述語」の場合) 関数を使用して、展開が終了したかどうかを判断hし、各要素に適用し、t(「変換」の場合) 要素をリストの残りのシードに変換します。

unfoldr展開が終了した場合にf :: b -> Maybe (a,b)返される単一の関数 、または がリストに追加する要素であり、リストの残りのシードであることが期待されます。NothingJust (x, y)xy

したがってf、は、 、およびunfoldrの 3 つすべての機能を担っています。-or-二分法はブール関数の役割を果たし、タプルの 2 番目の要素はリストの残りの部分にシードを供給するという役割を果たします。phtNothingJustpt

これが私の解決策です（明確にするために、質問の変数の名前を変更しました）：

listUnfold pred f trans seed =
    unfoldr (\x -> if pred x
                   then Nothing
                   else Just (f x, trans x)) seed

もちろん、値が定義の右端にある場合は、seedここにあるように、カリー化のための Haskell のセクシーな構文を利用して、完全に破棄することができます。

listUnfold pred f trans = unfoldr (\x -> if pred x
                                         then Nothing
                                         else Just (f x, trans x))

正式には、この変換はeta reductionとして知られています。

于 2013-03-21T00:19:16.813 に答える
2

の定義はunfoldr次のとおりです。

unfoldr                 :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b  =
  case f b of
   Just (a,new_b) -> a : unfoldr f new_b
   Nothing        -> []

そして、ガードの代わりにunfold使用するために少し書き直した Hutton のを次に示します。case

unfold :: (b -> Bool ) -> (b -> a) -> (b -> b) -> b -> [a]
unfold p h t x =
  case p x of
    True  -> []
    False -> h x : unfold p h t (t x)

いくつかの観察：

  • 型を比較す​​ると、同じ最終引数の型と同じ結果の型 unfoldrを共有していることがわかります。unfold
    • bの定義unfoldrとxの定義でunfoldは、基本的に同じ変数です。
    • 結果が同じになるように、2 つの関数の定義を一致させることもできれば幸いです。
  • 各関数は、case2 つの分岐を持つ式で構成されます。
  • 各関数では、これらの分岐の 1 つが になり[]ます。
    • だから、いつp x = True、欲しいf x = Nothing。
  • 各関数で、もう一方のブランチの結果は になり{-something-} : {-recursive-call-}ます。
    • だから、いつp x = False、欲しいf x = Just ({-something-}, {-something-else-})。

ここまでで が明確になったはずでありunfold p h t x = unfoldr f x where f = ...、推論の連鎖を続けて の定義を埋めることはそれほど難しくありませんf。

于 2013-03-21T00:42:51.987 に答える