# note to self: löb and möb

Working through the detail of Löb and möb: strange loops in Haskell and the related discussion on reddit.com/r/haskell, in particular psygnisfive’s comment. There’s nothing much original in this post, I’m just working through the details.

The LHS source for this post is here: https://github.com/carlohamalainen/playground/tree/master/haskell/loeb_and_moeb

In a spreadsheet one has a set of cells, and each cell can be defined in terms of values in the other cells. For example, let’s use four cells `x0`

, `x1`

, `x2`

, and `x3`

with the following definition:

The variable `xs0`

appears in a few places but it can be factored out. Remove `xs0 = 1`

and substitute the value `1`

in the definition for `xs`

. Also, `xs0`

is the first element of the `xs`

list, so refer to it using `xs !! 0`

:

Now do the same for `xs1`

:

The pattern should be clear, so now factor out `xs2`

and `xs3`

:

The common feature of the last three lines is that they are a function of `xs`

. The first line is the constant `1`

, and we can make this a function of `xs`

with something like

but the standard prelude provides `const 1`

for just this purpose. So now we have:

So each line is a function of `xs`

. Can we factor it out, in a sense, so each line looks more like the first? Yes:

The lambda expressions are a bit cumbersome. What we are doing is the succ function after selecting a certain element of a list. Haskell supports currying, and when one curries an operator, the left vs right arguments are respected:

```
*Main> :t (!!)
(!!) :: [a] -> Int -> a
*Main> :t (!! 3)
(!! 3) :: [a] -> a
```

So `succ (xs !! 0)`

can be rewritten as `succ . (!! 0) $ xs`

. Here is the next version:

We can still ask if there is a way to generalise the definition of `f5`

. Each line is of the form `function $ xs`

so we could define a list of functions

and then `xs = map (-> f xs) fs`

. In full:

Finally, the lambda expression is a bit clunky and Haskell provides the dollar-sign operator for function application (which is all the lambda expression is actually doing). With currying we get an appropriate type:

```
*Main> :t ($)
($) :: (a -> b) -> a -> b
*Main> :t ($ [1, 2, 3])
($ [1, 2, 3]) :: Num t => ([t] -> b) -> b
```

so `($ xs)`

will be a function that takes a function that operates on a list and returns something (as long as `xs`

is a list). This is just what we need:

and this is the final form in psygnisfive’s comment.

(Embarrassingly for myself, I had assumed that the type of `(!! xs)`

would be the result of currying on its *left-hand* parameter, not the right, which made the `map ($ xs) fs`

form incomprehensible.)

To finish things off, we’d like to write a function that computes the result `f6_2`

given the list `fs`

. Here’s a first attempt:

An alternative to using a let definition is to use a where (this brings us closer to the form given by quchen):

Looking at the type of loeb2,

shows the fact that we used a list as the starting point for the derivation. The first parameter is a list of functions that take a list and produce a value (of the same type), and the result is list. The final remark in psygnisfive’s comment is “rinse and repeat for your favourite functor.” What this refers to is the fact that map is specialised for lists. Functors generalise the idea of being able to “map over” something, and fmap generalises map:

```
*Main> :t map
map :: (a -> b) -> [a] -> [b]
*Main> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
*Main> map (+2) [1, 2, 3]
[3,4,5]
*Main> fmap (+2) [1, 2, 3]
[3,4,5]
*Main> :m Data.Maybe
Prelude Data.Maybe> fmap (+1) (Just 3)
Just 4
Prelude Data.Maybe> fmap (+1) Nothing
Nothing
```

Changing map to `fmap`

in the definition of `loeb2`

gets us the actual definition of `loeb`

:

For what it’s worth, putting `f = []`

specialises to the type signature of the earlier `loeb2`

:

which can be rewritten in the usual form

It doesn’t end! You can then abstract out the `fmap`

by making it a parameter, which gives the `moeb`

function:

See the discussion on reddit for motivation and possible uses of moeb.