3

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

变量：AB
常量：无
公理：A
规则：(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但我无法理解代码（还）并且还发现了其他同样令人困惑的实现。

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

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

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

4

2 回答 2

5

您可以使用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
于 2015-10-15T11:24:38.567 回答
4

我想你可能也对如何有效地生成一个实际的无限列表感兴趣，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]
于 2015-10-15T16:39:54.860 回答