将(可能是一元的)函数递归地应用到自身上

Question

我试图在Haskell中表达一个L系统https://en.m.wikipedia.org/wiki/L-system,特别是Lindenmayer的原始L系统,用于模拟藻类的生长.

变量:AB
常数:无
公理:
规则:(A→AB),(B→A)

对我来说,解决这个问题的自然方法是将规则应用于列表中的每个元素,这对我来说意味着我可以使用某种类型的字符串替换来对解决方案进行建模.

例:

对于"字符"列表[A,B,A我们应用规则并获得[A→AB,B→A,A→AB] = [A,B,A,A,B](对于此模型为了与Haskell很好地配合,你必须将AB视为列表[A,B],我们将与上述规则产生的任何其他结果相结合.

我已经生成了下面的代码,其中包含数据构造函数,不必处理除A或B之外的其他字符,

data Letter = A | B deriving (Show, Eq)

type Alphabet = [Letter]

algae :: Alphabet -> Alphabet

algae = concat . map (\c -> if
                | c == A -> A:[B]
                | c == B -> [A])

上面的代码是这样的,用自己作为参数调用它会产生预期的结果,即.那

algae $ algae $algae [A] =  [A, B, A, A, B]

重复的应用程序按预期工作.

我接下来要完成的是将函数递归地应用到自身,但未能表达这一点.通过这个我的意思是我希望能够调用该函数,无论是algae [A]或者只是algae(这需要更改类型签名algae :: Alphabet),这会产生一个无限的列表,通过将藻类无限次地应用到自身上来获得这个列表.

由于我已经承认失败,我已经查看了http://hackage.haskell.org/package/lindenmayer-0.1.0.0/docs/Lindenmayer-D0L.html但是我无法理解代码,因为它(还)还找到了其他代码同样令人困惑的实施.

我已尽力尝试使用使用folds和fix功能,但未能这样做.我也尝试借用其他递归定义,比如

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

但是这种方法失败了,因为zipWith需要二元运算符.没有monads可以解决这个问题吗？如果是这样,怎么样？

Answer 1

你可以用iterate.我还建议稍微修改你的algae函数来使用模式匹配:

data Letter = A | B deriving (Show, Eq)

type Alphabet = [Letter]

algae :: Alphabet -> Alphabet
algae = concatMap f
  where f A = [A, B]
        f B = [A]

infAlgae :: [Alphabet]
infAlgae = iterate algae [A]

main :: IO ()
main = print $ infAlgae !! 3