递归地将（可能是一元的）函数应用于自身

Question

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

variables : A B
constants : none
axiom : A
rules : (A → AB), (B → A)

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

示例：

对于列表 "characters" [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，但我（目前）还不能理解代码，并且还发现了其他同样令人困惑的实现。

我已尽力尝试使用 using folds 和 fix 函数，但未能成功。我还尝试借鉴其他递归定义，例如

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

但是这种方法失败了，因为 zipWith 需要一个二元运算符。没有 monad 可以解决这个问题吗？如果可以，怎么做？

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

Answer 2

我想您可能也对如何有效地生成实际的无限列表感兴趣，fibs 样式：

import Data.List (stripPrefix)

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

type Alphabet = [Letter]

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

infFromPrefix :: Eq a => ([a] -> [a]) -> [a] -> [a]
infFromPrefix rule prefix = inf where
    inf = prefix ++ case stripPrefix prefix (rule inf) of
        Just suffix -> suffix
        Nothing     -> error "Substitution does not preserve prefix"

infAlgae :: Alphabet
infAlgae = infFromPrefix algae [A]

main :: IO ()
main = print . take 100 $ infAlgae

在 GHCi 中：

*Main> :main
[A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,A,B,A,B,A,A,B,A,B,A,A,B,A]

递归地将（可能是一元的）函数应用于自身

Applying a (possibly unary) function recursively onto itself

haskell

grammar

l-systems

示例：