HW:以特定方式展开列表

Question

在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获取一个列表(x:xs)应该自己x作为头部和xs尾部进行处理.

p/s:我可能非常非常错误.

Answer 1

你差不多了!原始函数使用函数p(用于'谓词')来确定我们是否已完成展开,h应用于每个元素,以及t(对于"转换")将元素转换为列表其余部分的种子.

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

所以f在unfoldr负责所有三个的功能p,h和t.本Nothing-或- Just二分法扮演的布尔函数的一部分p了,元组的第二个元素做t的提供了列表的其余部分种子的工作.

这是我的解决方案(为了清楚起见,我已将您问题中的变量重命名):

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

当然,当一个值出现在定义的右端时,就像seed这里一样,你可以利用Haskell的性感语法进行currying并完全扔掉它:

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

形式上,这种转变被称为eta减少.