递归地应用一个（可能是一元的）函数 [英] Applying a (possibly unary) function recursively onto itself

问题描述

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

变量：AB

常量：无

公理：A
规则：（A→AB），（B→A）

对我来说，解决这个问题的自然方法是将规则应用到列表中的每个元素，这对我来说意味着我可以使用一些类型的字符串替换。

示例：

对于字符列表[A，B，我们将应用这些规则并得到[A→AB，B→A，A→AB] = [A，B，A，A，B]（对于这个模型和Haskell一起玩的很好，你必须把AB作为列表[A，B]，我们将结合上述规则生成的任何其他结果）。

我制作了代码公司在下面完整的数据构造函数中，不必处理除A或B之外的其他字符，

  data数据Letter = A | B导出（Show，Eq）
 
类型Alphabet = [Letter] 
 
藻类::字母表 - >字母
 
 algae = concat。 map（\c  - > if 
 | c == A  - > A：[B] 
 | c == B  - > [A]）
  

上面的代码是这样的，即将其自身作为参数调用会产生预期的结果。那

$ $ p $ $ $ $ $ $ $藻$ $藻类$藻$ [A] = [A，B，A，A，B]

重复申请按预期工作。

我想完成的其次是函数递归地应用于自身，但未能表达这一点。通过这个我的意思是我希望能够调用函数，或者作为藻类[A] 或者只是藻类（需要将类型签名更改为 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 预计一个二元运算符。
这个问题能解决没有单子吗？如果是这样，怎么样？

解决方案

您可以使用 iterate 。我还建议对藻类函数稍作修改以使用模式匹配：

  data Letter = A | B导出（Show，Eq）
 
类型Alphabet = [Letter] 
 
藻类::字母表 - > Alphabet 
 algae = concatMap f 
其中f A = [A，B] 
f B = [A] 
 
 infAlgae :: [Alphabet] 
 infAlgae = iterate algae [A] 
 
 main :: IO（）
 main = print $ infAlgae !! 3 
  

I am trying to express an L-system in Haskell https://en.m.wikipedia.org/wiki/L-system, specifically Lindenmayer's original L-system for modelling the growth of algae.

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

For me the natural way to approach this problem is to apply the rules to each element in the list, which (to me) means that I could model the solution using some type of string substitution.

Example:

For the list of "characters" [A, B, A we'd apply the rules and get [A → AB, B → A, A → AB] = [A, B, A, A, B] (for this model to play along nicely with Haskell you will have to regard AB as a list [A, B] which we will combine with any other results produced with the rules above).

I have produced the code included below which is complete with data constructors to not have to handle other characters than A or 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])

The above code is such that calling it with itself as an argument yields the expected result, viz. that

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

Repeated applications work as expected.

What I want to accomplish next is for the function to apply recursively onto itself, but have failed to express this. By this I mean that I would like to be able to call the function, either as algae [A] or just algae (which would require a type signature change to algae :: Alphabet) which yields an infinite list that one would receive by applying algae onto itself infinitely many times.

Since I have admitted defeat I have looked at http://hackage.haskell.org/package/lindenmayer-0.1.0.0/docs/Lindenmayer-D0L.html but I cannot comprehend the code as it is (yet) and also found other equally confusing implementations.

I've tried my best to attempt to use using folds and the fix function but have failed in doing so. I have also tried to borrow from other recursive definitions such as

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

But that approach fails since zipWith expects a binary operator. Can this problem be solved without monads? If so, how?

解决方案

You can use iterate. I would also suggest a slight modification to your algae function to use pattern matching:

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 

这篇关于递归地应用一个（可能是一元的）函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！