Применение (возможно, унарной) функции рекурсивно к себе

Question

Я пытаюсь выразить L-систему в Haskell https://en.m.wikipedia.org/wiki/L-system, в частности, оригинальную L-систему Линденмайера для моделирования роста водорослей.

переменные: A B
константы: нет
Аксиома: А
правила: (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 ожидает бинарный оператор. Можно ли решить эту проблему без монад? Если так, то как?

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]