在haskell中手工实现级联

Question

如何手工实现Haskell中的级联操作符？到目前为止，这就是我所拥有的，但我最终还是在与递归作斗争：

data MyList a = Empty | Element a (MyList a)
 deriving Show

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty Empty = Empty
concatenation a Empty = a
concatenation Empty a = a
concatenation x y = ???

Answer 1

我们可以对构造函数进行枚举，而不是直接使用变量。因此，我们需要涵盖四个案件：

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty Empty = -- ...
concatenation Empty (Element b bs) = -- ...
concatenation (Element a as) Empty = -- ...
concatenation (Element a as) (Element b bs) = -- ...

现在我们的目标是解决这些案件。连接两个Empty列表将返回一个空列表，因此Empty。

concatenation Empty Empty = Empty

如果第一个列表是Empty，而后者不是，那么我们返回第二个列表。

concatenation Empty (Element b bs) = Element b bs

如果第一个元素是一个列表，而后者不是，那么我们可以返回第一个列表：

concatenation (Element a as) Empty = Element a as

最后，如果两个列表都是非空的，则生成的列表从第一个列表的第一个元素开始，然后连接第一个列表的尾部，然后是第二个列表：

concatenation (Element a as) (Element b bs) = Element a (concatenation as (Element b bs))

这为我们提供了以下代码：

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty Empty = Empty
concatenation Empty (Element b bs) = Element b bs
concatenation (Element a as) Empty = Element a as
concatenation (Element a as) (Element b bs) = Element a (concatenation as (Element b bs))

我们可以用as模式缩短实现。

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty Empty = Empty
concatenation Empty bl@(Element b bs) = bl
concatenation al@(Element a as) Empty = al
concatenation (Element a as) bl@(Element b bs) = Element a (concatenation as bl)

但是这相当冗长，而且它对两个列表都执行模式匹配，这可能很昂贵:例如，如果第二个列表首先需要昂贵的计算，而第一个列表足够长(甚至无限长)，那么无论如何我们都不会对第二个列表感兴趣。

因此，我们可以看看是否可以压缩条款的数量。前两行可以分组，如下所示：

concatenation Empty Empty = Empty
concatenation Empty (Element b bs) = Element b bs

至：

concatenation Empty bl = bl

因为不管第二个列表的值如何，我们都会返回它。它还为我们节省了一个潜在的评估，这可能会导致更有效的代码。

我们能用最后两行做类似的事吗？

concatenation (Element a as) Empty = Element a as
concatenation (Element a as) bl@(Element b bs) = Element a (concatenation as bl)

因此，两者都有一个Element构造函数，a作为第一个元素。由于as和Empty的连接最终是concatenation as Empty = as，因此我们也可以在前一种情况下执行递归调用，并使用：

concatenation (Element a as) bl = Element a (concatenation as bl)

其结果是：

concatenation :: MyList a -> MyList a -> MyList a
concatenation Empty bl = bl
concatenation (Element a as) bl = Element a (concatenation as bl)

我们可以在这里省略第二个参数：

concatenation :: MyList a -> MyList a -> MyList a
concatenation Empty = id
concatenation (Element a as) = Element a . concatenation as

注意，最后一次减少本身并不是更有效:这可能导致将一个(可能很大的)列表的整个副本构造到内存中，如果第二个列表是空的，则会进行大量的计算。另一方面，如果计算第二个列表会导致陷入无限循环或昂贵的计算，而我们对这个部分不感兴趣，那么我们可以节省大量的CPU周期。

Answer 2

只需使用标准递归：

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty l = l
concatenation (Element e l1) l2 = Element e (concatenation l1 l2)

为什么要停下来？第二个规则一个接一个地获取第一个列表的每个元素，并在连接Empty和第二个列表之前嵌套它，即第二个列表本身(第一个规则)。

  concatenation Element 1 (... Element n (Empty)) l2
= Element 1 (concatenation Element 2 (... Element n (Empty))) l2 -- second rule
= ...
= Element 1 (Element 2 (... Element n (concatenation Empty l2))) -- second rule
= Element 1 (Element 2 (... Element n (l2))) -- first rule