5

我遇到了一种模式，我从一个种子值开始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

4 回答 4

11

如前所述，您想要的功能是unfoldr. 顾名思义，它与 相反foldr，但确切地了解为什么它是正确的可能是有启发性的。这是 的类型foldr：

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

前两个参数是获取类型的方法b，对应于列表的两个数据构造函数：

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

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

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

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

现在，只需反转两个转换的方向：

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

结果正是 的类型unfoldr。

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

于 2012-09-25T20:36:57.763 回答
6

您正在寻找的标准功能称为展开器。

于 2012-09-25T20:15:36.640 回答
5

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

在您的情况下，您想出了所需的 type (a -> (a, b)) -> a -> [b]。输入它不会产生任何结果 - 嗯。

好吧，也许有一个语法略有不同的标准函数。例如，标准函数的参数可能会翻转；让我们在某处寻找(a -> (a, b))其类型签名中的东西。这次我们很幸运，因为有很多结果，但是它们都在异国情调的包装中，而且似乎没有一个很有帮助。

也许你的函数的第二部分是一个更好的匹配，毕竟你想从一些初始元素中生成一个列表 - 所以输入a -> [b]并点击搜索。第一个结果：unfoldr- 宾果！

于 2012-09-25T20:59:20.150 回答
2

另一种可能性是iterateM在Statemonad：

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

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

所以你my_iter是

evalState . sequence . repeat :: State s a -> s -> [a]
于 2012-09-25T20:45:07.400 回答