Title: Theory / Unimportant / CS / Programming / Haskell / blog=
Tags: seen_description

Question: How to transform a recursive data type (such as AST) into a generic type on which morphisms can be used. Example:
data Expr = Index Expr Expr | Call Expr [Expr] | Unary String Expr | Binary Expr String Expr | Paren Expr | Literal Lit deriving (Show, Eq)
Answer: Replace the type by a variable as in
data ExprF a = Index a a | Call a [a] | Unary String a | Binary a String a | Paren a | Literal Lit deriving (Show, Eq)
Page: https://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/
Context: Haskell
Answer2: Take a fixpoint of the parametrized type
newtype  f = In { out :: f (Expr f) }

Instruction: >>>
Page: https://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/
Language: Haskell
Returns: flip (.)

Typ: Coalgebra f a
Meaning: a -> f a
Page: https://blog.sumtypeofway.com/recursion-schemes-part-2/
Language: Haskell
Example: (:: [])

Typ: Algebra f a
Meaning: f a -> a
Page: https://blog.sumtypeofway.com/recursion-schemes-part-2/
Language: Haskell

Page: https://blog.sumtypeofway.com/recursion-schemes-part-2/
Implementation: In < fmap (f? f) <<< f
Variables: f functor
a type
Name: anamorphism
Language: Haskell
Instruction: ana
Typ: Coalgebra f a -> a -> Term f
Intuition: unfold

Page: https://blog.sumtypeofway.com/recursion-schemes-part-2/
Implementation: out >>> fmap (cata f) >>> f
Variables: f functor
a type
Name: catamorphism
Language: Haskell
Instruction: cata
Typ: Algebra f a -> Term f -> a
Intuition: foldr
Implementation2: para'' . const

Question: Laws of catamorphism
Answer: cata In = id
Page: https://blog.sumtypeofway.com/recursion-schemes-part-2/
Variables: f functor
a type
Answer2: -- given alg :: f a -> a
-- and func :: f a -> f
cata (alg >>> fmap func)
is equal to
(cata alg) >>> func
Answer3: -- given alg :: f a -> a
-- and func :: f a -> g a
cata (f >>> In) >>> cata g
is equal to
cata (f >>> g)

Typ: RCoalgebra
Page: https://blog.sumtypeofway.com/recursion-schemes-part-2/
Language: Haskell
Variables: f functor
a type
Term a type ( * -> *)
Implementation: type T f a = a -> f (Either (Term f) a)
Intuition: Allow to use both recursive result and its input to compute current value

Page: https://blog.sumtypeofway.com/recursion-schemes-part-2/
Implementation: f? rAlg = In <<< fmap (id ||| 'F f) <<< f
Variables: f functor
a type
Term a type ( * -> *)
Name: apomorphism
Language: Haskell
Instruction: apo
Typ: (Functor f) => RCoalgebra f a -> Term f -> a
Implementation2: futu (fmap (either termToCoattr Continue) <<< f) where
  termToCoattr = Manual <<< fmap termToCoattr <<< out

Page: https://blog.sumtypeofway.com/recursion-schemes-part-2/
Implementation: f? rAlg = out >>> fmap (id &&& f? rAlg) >>> rAlg
Variables: f functor
a type
Term a type ( * -> *)
Name: paramorphism
Language: Haskell
Instruction: para
Typ: (Functor f) => RAlgebra f a -> Term f -> a
Implementation2: \f -> histo (fmap worker >>> f) where
  worker (Attr a h) = (In (fmap (worker >>> fst) h), a)

Typ: Attr f a
Language: Haskell
Implementation: T? { attribute :: a,
  hole :: f (T? f a)
}
Intuition: A recursive type, with some auxiliary value

Typ: CoAttr f a
Language: Haskell
Implementation: data T? f a =
  | Automatic a
  | Manual (f (T? f a))
Intuition: A recursive type, with some auxiliary value

Typ: CVAlgebra f a
Page: https://blog.sumtypeofway.com/recursion-schemes-part-iv-time-is-of-the-essence/
Language: Haskell
Implementation: f (Attr f a) -> a

Typ: CVCoAlgebra f a
Page: https://blog.sumtypeofway.com/recursion-schemes-part-iv-time-is-of-the-essence/
Language: Haskell
Implementation: a -> f (Attr f a)

Page: https://blog.sumtypeofway.com/recursion-schemes-part-iv-time-is-of-the-essence/
Implementation: f? h = In <<< fmap worker <<< f where
  worker (Automatic a) = futu f a
  worker (Manual g) = In (fmap worker g)
Name: futumorphism
Language: Haskell
Instruction: futu
Typ: Functor f => CVCoAlgebra f a -> a-> Term f
Etymology: Computation which can sometime decide a part of the future of the computation

Page: https://en.wikibooks.org/wiki/Haskell/Fix_and_recursion
Implementation: let {x = f x} in x
Variables: f :: (a -> a)
Language: Haskell
Returns: the fixpoint of applying f to its own result
Instruction: fix f

Question: Result of
fix (const "hello")
Answer: "hello"
Page: https://en.wikibooks.org/wiki/Haskell/Fix_and_recursion

Question: Result of
fix (const (1:))
Answer: [1, 1, ...
Page: https://en.wikibooks.org/wiki/Haskell/Fix_and_recursion

Question: Result of
fix (const (2+))
Answer: Stack overflow
Page: https://en.wikibooks.org/wiki/Haskell/Fix_and_recursion

Question: Result of
fix (\x -> take 2 $ cycle (1:x))
Answer: [1,1]
Page: https://en.wikibooks.org/wiki/Haskell/Fix_and_recursion