代码之家 › 专栏 › 技术社区 › hugomg

如果“输出”值与被迭代的值不同,那么prelude的迭代有什么替代方案?

haskell

hugomg · 技术社区 · 12 年前

我遇到了一种模式,我从种子值开始 x 并且在每个步骤生成新的种子值和要输出的值。我想要的最终结果是输出值的列表。这可以用以下函数表示:

my_iter :: (a -> (a, b)) -> a -> [b]
my_iter f x = y : my_iter f x'
   where (x',y) = f x

使用这个方法的一个人为例子是生成斐波那契数:

fibs:: [Integer]
fibs = my_iter (\(a,b) -> let c = a+b in ((b, c), c)) (0,1)
-- [1, 2, 3, 5, 8...

我的问题是,我有一种感觉,很可能有一种更习惯的方式来做这类事情。我的功能有哪些惯用的替代方案?

我现在能想到的只有 iterate 从前奏曲,但他们有一些缺点。

一种方法是先迭代,然后映射

my_iter f x = map f2 $ iterate f1 x
    where f1 = fst . f
          f2 = snd . f

然而,如果没有自然的方法将f分解为单独的f1和f2函数,这可能看起来很难看。(在人为的斐波那契情况下,这很容易做到,但在某些情况下,生成的值不是种子的“独立”函数,因此拆分事物并不那么简单)

另一种方法是将“输出”值与种子一起元组化,并使用单独的步骤来分离它们(有点像排序事物的“施瓦茨变换”):

my_iter f x = map snd . tail $ iterate (f.fst) (x, undefined)

但这似乎更糟糕,因为我们必须记住忽略生成的值,以便获得种子((f.fst)位)并添加,因此我们需要第一个“未定义”值,即伪生成值。

4 回复 | 直到 12 年前

hugomg 12 年前

如前所述,您想要的功能是 unfoldr .顾名思义,它与 foldr ,但看看为什么这是真的可能会很有启发性。这是类型 折叠器 以下为:

(a -> b -> b) -> b -> [a] -> b

前两个论点是获得某种类型的东西的方法 b ,对应于列表的两个数据构造函数:

[]  :: [a]
(:) :: a -> [a] -> [a]

…其中每次出现 [a] 被替换为 b 。注意到 [] 案例产生一个 b 在没有输入的情况下,我们可以将两者合并为一个函数 Maybe (a, b) 作为输入。

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

额外的括号表明,这本质上是一个将一种转换转换为另一种转换的函数。

现在,只需反转两个变换的方向:

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

结果正是 展开器 。

此演示的基本思想也可以类似地应用于其他递归数据类型。

Roman Cheplyaka 12 年前

您要查找的标准函数称为 unfoldr 。

David 12 年前

Hoogle 在这种情况下是一个非常有用的工具,因为它不仅支持按名称搜索函数,还支持按类型搜索函数。

在你的案例中,你想出了想要的类型 (a -> (a, b)) -> a -> [b] 。输入它不会产生任何结果-嗯。

也许有一个标准函数的语法略有不同。例如,标准函数的参数可能被翻转;让我们找一些 (a -> (a, b)) 在某个地方的类型签名中。这一次我们很幸运,因为有很多结果,但所有这些都是异国情调的包装,似乎没有一个很有帮助。

也许函数的第二部分更匹配,毕竟你想用一些初始元素生成一个列表,所以输入 a -> [b] 然后点击搜索。第一个结果: unfoldr -宾果游戏!

nponeccop 12 年前

另一种可能性是 iterateM 在里面 State 莫纳德:

iterateM :: Monad m => m a -> m [a]
iterateM = sequence . repeat

它不在标准库中,但很容易构建。

所以你的 my_iter 是

evalState . sequence . repeat :: State s a -> s -> [a]