haskellcatamorphismrecursion-schemes# Haskell cata types

After reading (and implementing) part of http://blog.sumtypeofway.com/recursion-schemes-part-2/ I still wonder how the types in the `cata`

function work. The `cata`

function is defined as:

```
mystery :: Functor f => (f a -> a) -> Term f -> a
mystery f = f . fmap (mystery f) . unTerm
```

I have something like `Term Expr`

. After unpacking I get `Expr (Term Expr)`

. The algebra (`f`

) is defined e.g. as `f :: Expr Int -> Int`

. I know I could call the following easily:

```
x = Literal "literal" :: Expr a
f :: Expr Int -> Int
f x :: Int
```

I can also imagine:

```
x = Literal "literal" :: Expr (Term Expr)
f :: Expr a -> Int
f x :: Int
```

But the following I suppose wouldn't work:

```
x = Literal "literal" :: Expr (Term Expr)
f :: Expr Int -> Int
f x :: ???
```

However, I still don't get how it works in the `cata`

function - how do I get from `Expr (Term Expr)`

to `Expr a`

. I understand that the values do work, but I just don't get the types - what happens in the leaves of the tree? This is indeed a `mystery`

...

Edit: I'll try to state more clearly what I don't understand.

Mentally, the `cata`

seems to work this way:

- Apply
`fmap f`

to leaves. - Now I have
`Expr Int`

and I can call`fmap f`

to the node I have and get way up.

It doesn't obviously work this way as I am applying `fmap (cata f)`

. However, ultimately the function `f`

gets called with `Expr Int`

as an argument (in the leaves). How was this type produced from `Expr (Term Expr)`

that it was before?

Solution

This is how `cata`

operates on leaves.

Assume `f :: Expr Int -> Int`

. Then:

```
cata f :: Term Expr -> Int
fmap (cata f) :: Expr (Term Expr) -> Expr Int
```

Now, for any function `g :: a -> b`

, we have

```
fmap g :: Expr a -> Expr b
fmap g (Literal n) = Literal n
...
```

So, on literals, `g`

is immaterial. This means that, choosing `a ~ Term Expr`

, `b ~ Int`

and `g = cata f`

we have

```
fmap (cata f) (Literal n) = Literal n :: Term Int
f (fmap (cata f) (Literal n)) = f (Literal n) :: Int
```

So, roughly, on leaves `fmap (cata f)`

is a no-op, but it changes the type from `Expr (Term Expr)`

to `Expr Int`

. This is a trivial transformation since `Literal n :: Expr a`

for any `a`

.

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code