External Publication
Visit Post

Free-like data structure:

Haskell Community [Unofficial] April 30, 2026
Source

You can view the normal free monad as a kind of tree structure. If you use the functor f a = (a, a) then it actually is just a binary tree. Notably, this tree is not necessarily balanced.

If you use the same functor f a = (a, a) in your free-like structure then you get a classic nested data type encoding of perfect binary trees.

If you consider f = State s then your free-like structure is a stateful computation where you have to specify the exact number of put and get operations that you will use before hand. In the normal free monad you can use a different number of these operations based on the intermediate results of the operations.

For example you can write this program with Free, but not with your free-like structure:

countdown :: Free (State Int) ()
countdown = do
  x <- get
  when (x > 0) $ do
    put (x - 1)
    countdown

In this program the number of get and put operations depends on the value of the state you start with.

Discussion in the ATmosphere

Loading comments...