haskell - 将(可能是一元的)函数递归地应用于自身

Question

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

variables : A B
constants : none
axiom : A
rules : (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 需要一个二元运算符。没有单子(monad)可以解决这个问题吗？如果有，怎么做？

Answer 1

您可以使用迭代。我还建议对您的 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