At the bottom of the page, the link should be: https://blog.sumtypeofway.com/posts/recursion-schemes-part-3.html
Instead I get a 404 error, it tries to link me to: http://blog.sumtypeofway.com/recursion-schemes-part-iii-folds-in-context/

Stop is mentioned a few times but never declared. I think this should be changed to Manual?
Also in 1 snippet, the grow function returns only a 2-tuple, while it should return a 3-tuple (this is corrected in the later snippets).

It's some nitpicking, but this initially confused me while reading through that section 😅.

change :: Cent -> Int
change amt = histo go (expand amt) where
  go :: Nat (Attr Nat Int) -> Int
  go Zero = 1
  go curr@(Next attr) = let
    given = compress curr
    validCoins = filter (<= given) coins
    in sum (map (lookup attr) validCoins)

lookup :: Attr Nat a -> Int -> a
lookup cache 1 = attribute cache
lookup cache n = lookup inner (n - 1) where (Next inner) = hole cache

"Here’s the kicker: our above CoAttr definition is equivalent to the Free monad, and Attr (being dual to CoAttr) is the Cofree comonad."

How can change be re-written in terms of Cofree? I pulled in recursion-schemes but I'm having trouble getting this to work:

type Cent = Int

coins = [Cent]

coins = [100,50,25,10,5,1]

change :: Natural -> Natural
change amt = histo go amt where
  go :: Maybe a -> Natural
  go Nothing = 1
  go curr@(Just attr) = let
    given = _curr
    validCoins = filter (<= given) coins
    in sum (map (lookup attr) validCoins)
  lookup cache 0 = _attribute
  lookup cache n = lookup inner (n - 1) where (Just inner) = _hole

Thanks

Perhaps ' is missing in flatten' definition.
Do you mean

flatten' :: Expr -> Expr
flatten' (Paren e) = flatten' e
flatten' x = applyExpr flatten' x

instead of

flatten' :: Expr -> Expr
flatten' (Paren e) = flatten e
flatten' x = applyExpr flatten x

?

Hi, I stumbled upon your intro series to recursion schemes and so far it is an enlightening read. However, I notice that there are some errors in the code for Coin Change Problem in part 4 of the series.

First, normally Coin Change Problem asks for the number of ways one can make the change of a fixed amount that is insensitive to the order where a coin is being listed. Eg. there are only 2 ways to make a change of amount 6:
[1, 5]
[1, 1, 1, 1, 1, 1]
Note that here [1, 5] and [5, 1] are counted as the same way.

However, the intention of your code seems to be sensitive to the order of the coins. Eg. there are 3 ways to make a change of amount 6:
[1, 5]
[5, 1]
[1, 1, 1, 1, 1, 1]

Secondly, the code to lookup cache is wrong. The code seems to incorrectly assume that the history is stored in such a way that the result of change 0 is stored at the outermost level, result of change 1 is stored at the second outermost level, ..., and the result of change (given - 1) is stored at the innermost level. However, the reverse is true. That is, the result of change (given - 1) is stored at the outermost level and the result of change 0 is stored at the innermost level.

Below is a modified code that correctly solves the Coin Change Problem variant where the order of the coins in the change matters.

change :: Cent -> Int
change amt = histo go (expand amt) where
  go :: Nat (Attr Nat Int) -> Int
  go Zero = 1
  go curr@(Next attr) = let
    given = compress curr
    validCoins = filter (<= given) coins
    in sum (map (lookup attr) validCoins)

lookup :: Attr Nat a -> Int -> a
lookup cache 1 = attribute cache
lookup cache n = lookup inner (n - 1) where (Next inner) = hole cache

Thank you for writing this excellent series!

I noticed that starting around here you start using Continue and Stop to refer to the CoAttr constructors in the text and in parts of the horticulture example code, whereas you have defined these constructors as Automatic and Manual.

When I run the change function from the section on futumorphisms, it reports that there are 3 ways to make change for 10 cents. But it seems like there are four: a dime, two nickels, a nickel and five cents, or ten cents.

That's the only error I see below 15. For numbers greater than 14 I suspect it might always be wrong:

> mapM_ (putStrLn . show) $ map (id &&& change) [0..16]
(0,1)
(1,1)
(2,1)
(3,1)
(4,1)
(5,2)
(6,2)
(7,2)
(8,2)
(9,2)
(10,3)
(11,4)
(12,4)
(13,4)
(14,4)
(15,4)
(16,4)

I just discovered your posts about recursion schemes. They are absolutely wonderful. Thank you so much.

I'm not sure whether the following are all in fact problems with the blog; it could be I just missed something. If I should post these somewhere else, please let me know.

The cata laws

In part 2 I'm confused by the laws. The first is stated as an equation: cata In = id. That's clear. But the second is stated as an implication:

-- given alg :: f a -> a
-- and func  :: f a -> f
cata (alg >>> fmap func) =>
   (cata alg) >>> func

Is that => symbol supposed to be =?

The third law's statement is even stranger:

-- given alg  :: f a -> a
-- and func :: f a -> g a
cata (f >>> In) >>> cata g
   ==> cata (f >>> g)

Is that ==> symbol again supposed to be =? And why does it stipulate types for alg and func, without ever using them?

Generalizing cata using para

This happens in section 3 of the blog series.
The code provided is this:

cata' :: Functor f => Algebra f a -> Term f -> a
cata' = para'' (const f)

But f is not defined, except as a type constraint.

Section II appears not to talk about ana

Section III claims Section II defined ana: "In the previous post, we defined ana, the anamorphism ...". Section 1 makes a similar claim. I'm not finding it.