3

在 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]

这与上面的类似，但在其实现中使用了展开器并且是非递归的。

我已经尝试了一段时间来解决上面的问题，但我仍然可以做到（在 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为真，则返回空列表。否则，h x用作头部并将展开器的结果附加为尾部。Unfoldr 将一个列表作为头部和尾部(x:xs)进行递归。xxs

p/s：我可能这样做非常非常错误。

4

2 回答 2

6

你几乎明白了！原始函数使用函数p（用于“谓词”）来确定我们是否已完成展开，h应用于每个元素，以及t（用于“转换”）将元素转换为列表其余部分的种子。

unfoldr需要一个函数，如果我们已经完成展开f :: b -> Maybe (a,b)，它会返回，或者，要添加到列表中的元素在哪里，并且是列表其余部分的种子。NothingJust (x, y)xy

所以finunfoldr负责 ,p和h的所有三个功能t。Nothing-or - Justdichotomy 扮演布尔函数的一部分，元p组的第二个元素负责t为列表的其余部分提供种子。

这是我的解决方案（为清楚起见，我已从您的问题中重命名变量）：

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 缩减。

于 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        -> []

这里是 Hutton 的unfold，稍微改写来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共享相同的最终参数类型和相同的结果类型。
    • bindefinitionunfoldr和xindefinitionunfold基本上是同一个变量。
    • 希望我们也可以匹配两个函数的定义，以使结果相同。
  • 每个函数由一个case表达式组成，有两个分支。
  • 在每个函数中，其中一个分支导致[].
    • 所以什么时候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 回答