Haskell:递归复制函数

Question

我刚刚开始使用Haskell.我正在尝试创建一个模仿replicateHaskell中的标准函数但使用递归的函数.例如,

Prelude> replicate 3 "Ha!"
["Ha!","Ha!","Ha!"]

它应该是类型Int -> a -> [a].到目前为止,我有:

myReplicate :: Int -> a -> [a]
myReplicate x y = y : myReplicate (x-1) y
myReplicate 0 y = [ ]

但是,我的函数总是生成无限列表:

Prelude> myReplicate 3 "Ha!"
["Ha!","Ha!","Ha!","Ha!","Ha!","Ha!","Ha!",...

Answer 1

你必须把第二个案例放在第一个案例之前,否则它永远不会进入第二个案例.

myReplicate :: Int -> a -> [a]
myReplicate 0 y = [ ]
myReplicate x y = y : myReplicate (x-1) y

Answer 2

您的代码应生成警告读数（至少在 GHC 中）：

Pattern match(es) are overlapped
In an equation for 'myReplicate': myReplicate 0 y = ...

发生的事情是代码尝试按照您编写的顺序（自上而下）将您的输入与您编写的每个定义进行匹配。当您编写 时f x = ...，该x变量将始终与它所代表的类型的任何值匹配。如果定义中的所有绑定都匹配，则将使用该定义。

在您的情况下，第一个定义是myReplicate x y = y : myReplicate (x-1) y. 正如我所说的，x并y会配合你通过任何价值，包括0为x绑定。@Alec 提出的解决方案展示了如何避免这个问题，先写最具体的模式，最后写全能模式。

另一种解决方案是使用警卫：

myReplicate :: Int -> a -> [a]
myReplicate x y
    | x > 0  = y : myReplicate (x-1) y
    | x == 0 = []
    | otherwise = [] -- or throw an exception, or use Maybe

通过这种方式，如果您正确编写条件（换句话说，如果条件是互斥的），您可以以任何顺序编写要使用的表达式。请注意，条件仍将首先从顶部评估，然后向下评估，直到条件为真，就像if ... else if ... else if ... else ...命令式语言中的链一样。