4

Haskell 中的unfold函数非常方便创建列表。它的定义是：

unfold :: (b -> Maybe (a, b)) -> b -> [a]

但我想获得使用的累加器的最后一个值。一个可能的实现是：

unfoldRest :: (b -> Maybe (a, b)) -> b -> ([a], b)
unfoldRest fct ini = go fct ini []
  where
    go f s acc =
      case f s of
        Nothing -> (acc, s)
        Just (a, b) -> go f b (acc ++ [a])

但我想知道是否没有办法使用现有功能来做到这一点。最后是这个：

countDown 0 = Nothing
countDown n = Just (n, n-1)
unfoldRest countDown 10

将返回：

([10,9,8,7,6,5,4,3,2,1],0)

因为当累加器值达到时迭代停止0。

4

3 回答 3

10 
import Data.List

unfoldr' :: (b -> Maybe (a, b)) -> b -> [(a, b)]
unfoldr' f = unfoldr (fmap (\(a, b) -> ((a, b), b)) . f)

将为您提供累加器的所有状态。然后你可以选择查看任何你想要的，包括最后一个。

于 2014-05-08T17:36:41.370 回答
3

这不是一个很好的答案（Tom Ellis 更好地涵盖了“使用现有功能的方法”部分），但值得再看一下您的原始解决方案。由于您使用(++)重复附加单个元素，因此生成列表的长度需要二次时间。您可以通过删除辅助函数并直接使用以下命令构建列表来避免这种情况(:)：

unfoldRest' :: (b -> Maybe (a, b)) -> b -> ([a], b)
unfoldRest' f s = case f s of
    Nothing -> ([], s)
    Just (a, b) -> (\ ~(xs, y) -> (a : xs, y)) $ unfoldRest' f b

惰性模式匹配（~(xs, y)在 lambda 中）很重要；它允许您查看列表的第一个元素而不必计算最终状态，因此可以对无限列表做一些有用的事情（无论如何，Tom Ellis 的解决方案对于无限列表更好，因为您可以看到只有生成的值，还有任何任意段之后的状态）。正如 Will Ness 指出的那样，您可能会发现使用绑定Just来编写案例的右侧更自然，如.letlet (xs, y) = unfoldRest' f b in (a : xs, y)

当您用“pointfree”标记问题时，值得一提的是，您可以通过使用maybe和Control.Arrow组合器减少很多点数：

import Control.Arrow ((***), first, app)

unfoldRest'' f s =
    maybe ([], s) (app . (first . (:) *** unfoldRest'' f)) $ f s

你是否想走那么远是一个品味问题。惰性问题得到了正确处理，因为(***)for 函数的实现使用了惰性模式匹配。

于 2014-05-08T18:52:53.770 回答
1

我之前已经解决过这个问题 - 解决它的方法之一是使用State monad。

简单来说，它们处理表单上的函数s -> (d, s)。直观地说，s是在计算过程中可能改变的状态类型。

首先要注意的是s -> Maybe (d, s)没有形式s -> (d, s)：前者是一个元组，而后者是一个Maybe，我们需要一个函数类型s -> (Maybe d, s)，如果函数返回None，修改后的函数将返回之前的状态。此适配器的一种可能实现是：

keepFailure :: (s -> Maybe (d, s)) -> (s -> (Maybe d, s))
keepFailure f s = maybe (Nothing, s) (first Just) (f s)

请记住，import Data.Bifunctor因为firstfunction 有一个函数可以将 from 转换s -> (d, s)为State s d被调用state，并将 runState其转换回来。现在我们实现一个函数，它将尝试耗尽所有可能值的状态：

stateUnfoldr :: State s (Maybe d) -> State s [d]
stateUnfoldr f = do
  mx <- f
  case mx of
    Just x -> do
      xs <- stateUnfoldr f
      return $ x:xs
    Nothing -> return []

简单来说，mx <- f就像“应用f到输入，更新状态，获取返回值给mx”然后，我们可以把所有东西拼凑在一起：

fStateUnfoldr :: (s -> Maybe (d, s)) -> (s -> ([d], s))
fStateUnfoldr f = runState $ stateUnfoldr $ state . keepFailure $ f

记得import Control.Monad.State

state . keepFailure适应Monad，然后展开为 a f，然后将其转回函数。State s (Maybe d)stateUnfoldrState s [d]runState

如果您只需要状态或列表，我们也可以使用execStateorevalState代替。runState

于 2021-01-26T02:57:44.747 回答