Haskell:递归复制函数

Question

我才刚刚开始接触Haskell。我正在尝试创建一个函数，它模仿Haskell中的标准replicate函数，但使用了递归。例如,

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将与您传递的任何值匹配，包括用于x绑定的0。@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 ...链。

Answer 3

您可以使用map：

myReplicate :: Int -> a -> [a]
myReplicate n x = map (const x) [1..n]

您也可以从Data.Functor使用$>：

import Data.Functor 
myReplicate :: Int -> a -> [a]
myReplicate n x = [1..n] $> x