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
module Loeb where
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:
f1 :: [Int]
f1 = let xs0 = 1
xs1 = succ xs0
xs2 = succ xs1
xs3 = succ xs2
xs = [xs0, xs1, xs2, xs3]
in xs
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:
f2 :: [Int]
f2 = let xs1 = succ (xs !! 0)
xs2 = succ xs1
xs3 = succ xs2
xs = [1, xs1, xs2, xs3]
in xs
Now do the same for xs1:
f3 :: [Int]
f3 = let xs2 = succ (xs !! 1)
xs3 = succ xs2
xs = [1, succ (xs !! 0), xs2, xs3]
in xs
The pattern should be clear, so now factor out xs2 and xs3:
f4 :: [Int]
f4 = let xs = [ 1
, succ (xs !! 0)
, succ (xs !! 1)
, succ (xs !! 2)
]
in xs
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
_ -> 1
but the standard prelude provides const 1 for just this purpose. So now we have:
f4_1 :: [Int]
f4_1 = let xs = [ const 1 $ xs
, succ (xs !! 0)
, succ (xs !! 1)
, succ (xs !! 2)
]
in xs
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:
f4_2 :: [Int]
f4_2 = let xs = [ const 1 $ xs
, succ . (h -> h !! 0) $ xs
, succ . (h -> h !! 1) $ xs
, succ . (h -> h !! 2) $ xs
]
in xs
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:
f5 :: [Int]
f5 = let xs = [ const 1 $ xs
, succ . (!! 0) $ xs
, succ . (!! 1) $ xs
, succ . (!! 2) $ xs
]
in xs
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
fs = [ const 1
, succ . (!! 0)
, succ . (!! 1)
, succ . (!! 2)
]
and then xs = map (-> f xs) fs. In full:
f6_1 :: [Int]
f6_1 = let fs = [ const 1
, succ . (!! 0)
, succ . (!! 1)
, succ . (!! 2)
]
xs = map (f -> f xs) fs
in xs
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:
f6_2 :: [Int]
f6_2 = let fs = [ const 1
, succ . (!! 0)
, succ . (!! 1)
, succ . (!! 2)
]
xs = map ($ xs) fs
in xs
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:
loeb1 fs = let xs = map ($ xs) fs in xs
An alternative to using a let definition is to use a where (this brings us closer to the form given by quchen):
loeb2 fs = go where go = map ($ go) fs
Looking at the type of loeb2,
loeb2 :: [[b] -> b] -> [b]
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:
loeb :: Functor f => f (f b -> b) -> f b
loeb fs = go where go = fmap ($ go) fs
For what it’s worth, putting f = [] specialises to the type signature of the earlier loeb2:
loeb :: [] ([] b -> b) -> [] b
which can be rewritten in the usual form
loeb :: [[b] -> b] -> [b]
It doesn’t end! You can then abstract out the fmap by making it a parameter, which gives the moeb function:
moeb :: t -> (((a -> b) -> b) -> t -> a) -> a
moeb fs x = go where go = x ($ go) fs
See the discussion on reddit for motivation and possible uses of moeb.