时间戳

首页 > 解决方案 > 2 个列表的串联

haskell - 2 个列表的串联

问题描述

我将列表类型定义为
data List a = Empty | Entry a (List a)

我需要写一个带有签名的函数
appendList :: List a -> List a -> List a

看起来递归在这里可能有用，但我不知道如何使用它

标签： haskell

解决方案

根据您的评论，您自己解决了大部分问题。

（将来）可能会有所帮助的是详尽地查看数据构造函数的所有组合。由于这里有两个参数，并且每个参数List a都有两个数据构造函数，因此我们可以写成骨架：

appendList :: List a -> List a -> List a
appendList Empty Empty = …
appendList Empty (Entry x xs) = …
appendList (Entry x xs) Empty = …
appendList (Entry x xs) (Entry y ys) = …

现在我们可以对这些情况进行推理。如果两个列表都是Empty，那么结果也是一个Empty列表。如果第一个列表是Empty，第二个是非空的，那么我们返回第二个列表。如果第一个列表非空，而第二个列表为空，则返回第一个列表。最后，如果两个列表都是非空的，我们创建一个列表，它将产生第一个列表的第一项，并在第一个列表的尾部和第二个列表上递归。

所以我们可以通过以下方式实现：

appendList :: List a -> List a -> List a
appendList Empty Empty = Empty
appendList Empty (Entry x xs) = (Entry x xs)
appendList (Entry x xs) Empty = (Entry x xs)
appendList (Entry x xs) (Entry y ys) = (Entry x (appendList xs (Entry y ys)))

我们现在可以压缩这些子句。例如，前两个子句可以通过简单地返回第二个列表来解决。第三个和第四个子句可以压缩到第二个参数是Entry x (AppendList xs ya)哪里：ya

appendList :: List a -> List a -> List a
appendList Empty ya = ya
appendList (Entry x xs) ya = (Entry x (appendList xs ya))

或者我们可以通过以下方式使其更紧凑：

appendList :: List a -> List a -> List a
appendList Empty = id
appendList (Entry x xs) = Entry x . appendList xs

推荐阅读