时间戳

首页 > 解决方案 > Haskell - 将列表转换为递归数据结构

haskell - Haskell - 将列表转换为递归数据结构

问题描述

我在 Haskell 教科书中发现了这个问题。给定一个递归数据结构：

data Foo = A Foo Foo | B Int Foo | C Int

创建一个函数：

createFooFromList :: [Int] -> Foo -> Foo

它接受一个列表和一个Foo，将列表应用于Foo，并返回新的Foo.

最好用一个例子来描述“应用”的含义。

假设我们有一个Foo定义为的B 0 (B 1 (A (B 0 (C 1)) (B 1 (C 1))))，我们必须将列表应用[0,0,1,0,2,0]到这个Foo。为此，只需取给定序列中的每个整数，然后用序列中的Foo这些整数按顺序替换结构中的整数。

所以对于上面的例子，我们的输出是B 0 (B 0 (A (B 1 (C 0)) (B 2 (C 0))))

到目前为止，我已经创建了一个将列表应用于BandC结构的函数。C是微不足道的，B也很容易，因为我只需将列表的头部设置为 的Int参数B，然后递归地将列表的其余部分应用于 的Foo部分B。但是我不确定如何处理A。

标签： haskellrecursiontreebinary-tree

解决方案

这里有一个提示：

我将首先编写一个辅助函数，该函数接受[Int]andFoo参数，不仅返回输出，还返回Foo一个[Int]表示输入列表中尚未使用的数字的附加函数。因此，生成的输出类型可以是一对。

这里的直觉是，这个辅助函数不假设输入[Int]列表包含正确数量的Foo输入，而是允许Int存在更多的 s，并返回超出的那些。

使用这个辅助函数，你可以处理里面A有两个Foos的情况：你在第一个上调用辅助函数Foo，得到多余Int的s，然后将它们用于第二个Foo，并返回新的多余Ints。

（更高级的方法是使用State [Int]monad，但上述基本方法应该没问题。）

推荐阅读