Löb and möb: strange loops in Haskell

This is a fairly free translation of the article. The fact is that despite the construction in one line, the material is difficult to understand.
Taking into account that in the comments of the Prelude or how to fall in love with Haskell, they asked that the code was clear, I made enough remarks, and I hope that the code will be clear to those who are far from Haskel.

Let's start with the most difficult - from the very title: many of his words are incomprehensible.
Haskell is a pure and lazy functional language.
Loeb is a German mathematician, which we will talk about later.
Well, and finally, the most interesting - strange loop.

Strange loops are tangled categories, when moving up or down in a hierarchical system, you find the same thing from where you started moving.
Often such loops contain self-referential links.
For example, recursive acronyms have such a strange loop: "PHP - PHP: Hypertext Preprocessor".
Well, today the most mysterious word containing strange loops is the notion of "I."

Strange loops excite people with their beauty. And it is very nice when you find them in the most unexpected places. Very interesting functions with strange loops can be written on Haskell.
')
The German mathematician Loeb migrated to Great Britain in the 39th year of the twentieth century. Loeb, in particular, developed mathematical logic and the world is primarily known for the Loeb Theorem. This theorem developed Godel's works on the incompleteness of mathematics. Loeb's theorem on the relationship between the provability of an assertion and the assertion itself, it states that

in any theory that includes Peano's axiomatics (the axiomatics about natural numbers), for any statement P provability of the statement “if provable P , then P true” is possible only in the case of provability of the statement P .

All this complexity of the statement can be written symbolically:


Is it possible to write such a function on Haskell ?! Can! And just one line!

Loeb

loeb is one of those functions on Haskele that looks charming, crazy, simple and complex at the same time.

1. The function is very easy to write
2. The function is difficult to understand
3. Easy to use function
4. Function is explainable

Implementation

Feel smart? Let's change this, introducing you to the loeb function:

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x 

Feel all beauty ?! Then skip to the next section.
Not? Hmm ... maybe you just do not know Haskell well? Then I will explain in more detail.
Some shrewd ones will ask why there are two lines here, not just one, and they will be right. But only partially. The fact is that the first line is the signature: the declaration, with which types, with how many parameters the function works. However, this line is optional - if you do not write it, the interpreter (and the compiler) themselves will display the types:

 loeb :: Functor f => f (fa -> a) -> fa 

The signature is divided into three parts - first we write the name of the function, then we say that we want to declare the type, put :: , then we’ll write restrictions on the parameters to the fat arrow ( => ) - I’ll explain it a little bit below until it matters. And finally - the types themselves:
f (fa -> a) -> fa , look how close the record is to the Loeb theorem: - yes one to one!
I note, the function is written without using library functions!

Before explaining what a signature means, as long as we go through the function itself, let's not waste time on trifles, and write the function in 3 lines, as any decent haskelist will do:

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x 

Here you can see that the word where is a service one and makes it possible to define an internal function.

How to read? ... Oh, yes, I must say that in Haskell there are no extra brackets, and where in most languages ​​they write
f (x, y, z) = ... , in Haskell they write only fxyz = ...

From the code it is clear that the loeb function is a function of one argument and it is determined through the function go .

The function go defined by the Functor and the function fmap . The fmap function itself is a generalization of the map function for lists and is defined as follows:

 class Functor f where fmap :: (a -> b) -> fa -> fb 

This is just a declaration. OOP classes have nothing to do with type classes. In our case, we don’t need to especially understand the first line, it just says that f will be polymorphic in the function fmap .
So look carefully at the signature, to understand what it means.
It is said that the function fmap is a function of two arguments - (a -> b) and fa , the output is type fb .
It is easy to understand that (a -> b) is a function of one argument, taking some value as an input (generally we call this type a , it can be any — for example, a string, a number, or a file) and the output is also some or a type (we denote it by b , remembering that b in particular may be a ).
fa - can be understood as a kind of complex value depending on a and it will be easier to understand if you read as f(a)
If you open the definitions of a functor in math, you will see surprising similarities.
That is, if we ignore the full understanding, and go to the intuitive one, it can be seen that the function fmap applies the function to the value through f , and, as a rule, it is so.

For our needs, it is not necessary to fully understand the full power of the functors, let's consider only the lists:

 instance Functor [] where fmap = map 

It came out easier - for lists, the fmap function fmap completely analogous to the map function. Well, the map function already all imperatives know, this application of the function to all the members of the list. In Haskell, it is determined very simply:

 map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = fx : map f xs 

We look at the signature: here everything is already familiar - a function of two arguments - a function of one parameter and a list. The result is a modified list.
The second line says that for an empty list, regardless of the function ("_" - we say that we do not need to know its value) will be an empty list.
For other cases, we can divide the list into head and the rest ( x : xs , notice the letter s , in English, this means the plural, they say many x -s in xs ) and return another list, where we use the function for the head, and tail we recursively apply our described function.



Well, go to our definition again:

 go = fmap ($ go) x 

What is the function with the dollar? Surely without Uncle Sam, and there was not enough? Well that you, same pure language! $ Is an ordinary function-operator, called an applicative function and is determined elementarily:

 ($) :: (a -> b) -> a -> b f $ x = fx 

No, it did not seem to you, the applicative function does nothing, but it is often used instead of brackets.

Well, so as not to confuse you, let's rewrite the loeb function using lambda expressions:

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap (\z -> z go) x 

It is easy to read the lambda expressions: \z -> z go means that the lambda function (a slash resembles the Greek letter lambda - λ ) from one variable z , and the arrow -> read like =

Great, we could read! Now it remains to understand her!

What is loeb doing?

Short version: loeb calculates the result in terms of itself, but this is more crazy than what you felt when you first heard about recursion.

Detailed version: What is loeb use for? Where is it useful? For example, you can make a spreadsheet (like Exel) for a list functor - []:

 xs :: [a] xs = [...] fs :: [[a] -> a] fs = [...] rs :: [a] rs = [ f xs | f <- fs ] -- r = f xs 

Suppose we have a list xs :: [a] . And we have a list of functions that collapse the lists to values, fs :: [[a] -> a] . We take and for each function from the list we apply to the list of elements, thus obtaining a new value r . Collect all r in the list rs .

 [ f xs | f <- fs ] 

it is difficult to understand, but still - we in each cell of the list apply the function (from the list) to the list of values, read from right to left.

For these actions, we calculated rs from the list of xs values ​​and the list of fs functions.

And now the most important thing - you can not take a list of xs values, and use rs instead. In other words, the function f is applied to the list of results, which itself generates!

 fs :: [[a] -> a] fs = [...] rs :: [a] rs = [ f rs | f <- fs ] 

Of course, this all relies on the strongest laziness, as long as rs is calculated in terms of itself. You can combine both functions to not have your own definitions of fs , and they will be just the rs parameter:

 rs fs = [ f (rs fs) | f <- fs ] 

If you look closely, then for lists rs = loeb

Thus, the loeb function takes a list of functions, and calculates a list of results that it generates, and applies itself to the list just generated. Strange? Check? Ringed? I bet no!

Examples with loeb

An example that will help you understand how to work with this function:

 fs = [ const 1 , succ . (!! 0) , succ . (!! 1) , succ . (!! 2) ] 

Here const a _ = a is a function of two variables, which always returns the value of the first, succ x = inc increment for numbers (more precisely, this is a generalization of the increment for any enumerated values), (!!) is the function of pulling the n element from the list , (.) - functional composition of 2 functions, first applies the right function, then the left one, in our case, first pulls an element from the list, then increments.

Here we have described the list of elements in terms of previous results. const 1 we have the first element, and it always returns 1, after that you can get the value of the second element - succ . (!! 0) succ . (!! 0) , and further along the chain - the third, fourth and fifth.

 > loeb fs [1,2,3,4] 

The interesting part is that the order does not necessarily have to be from left to right. The order can be inverted, the main thing is not to achieve circular recursion (in this case, the function will not be able to finish the calculations).

 fs = [ succ . (!! 1) , succ . (!! 3) , succ . (!! 0) , const 1 ] > loeb fs [3,2,4,1] 

Does the truth look like a spreadsheet ?! One value in the cell is known, and the others depend on each other in some way. When the calculation ends, each cell has a specific value. It looks like a generalization of a fixed point combinator.

Spreadsheets!

The above example is similar to a one-dimensional table. But you can take other functors that are closer to reality, arrays, for example!

 import Data.Array import Data.List import Control.Monad import Text.Printf loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x --   e = val 0 --     val = const -- ,   (10 %)    vat ix = (* 0.1) . (! ix) --    sum' ixs = \arr -> foldl' (\acc ix -> acc + arr ! ix) 0 ixs spreadsheet = listArray ((0,0), (4,4)) -- Prices | VAT | Effective prices + total [ val 1, vat (0,0), sum' [(0,i) | i <- [0..1]], e, e , val 3, vat (1,0), sum' [(1,i) | i <- [0..1]], e, e , val 5, vat (2,0), sum' [(2,i) | i <- [0..1]], e, e , val 2, vat (3,0), sum' [(3,i) | i <- [0..1]], e, e , e, e, sum' [(i,2) | i <- [0..3]], e, e ] printArr :: Array (Int, Int) Double -> IO () printArr arr = forM_ [0..4] $ \i -> do forM_ [0..4] $ \j -> printf "%4.1f " (arr ! (i,j)) printf "\n" main = printArr $ loeb spreadsheet 

Let's run!
At the output we get:

  1.0 0.1 1.1 0.0 0.0 3.0 0.3 3.3 0.0 0.0 5.0 0.5 5.5 0.0 0.0 2.0 0.2 2.2 0.0 0.0 0.0 0.0 12.1 0.0 0.0 

where in the first knee we have prices (using val ), in the second column we have taxes of what is left, in the third column the effective price, and below the total sum of all effective prices. Now you can see, order and buy everything! Magic! :-)

moeb function

moeb is the result of the game with the definition of the loeb function: what if we want to abstract from the fmap . For starters, this will make the signature under the function just crazy!

 -- [m]oeb = multi-loeb :-) moeb :: (((a -> b) -> b) -> c -> a) -> c -> a moeb fx = go where go = f ($ go) x 

And in new terms you can redefine loeb , it will only be a special case of moeb :

 loeb = moeb fmap 

And what other functions can be used for the parameter of the moeb function moeb that it can be used?
Well, for example, if we have a function

 id :: a -> a id x = x 

Then:

 moeb id x = id ($ moeb id x) x = ($ moeb id x) x = x (moeb id x) --    ,   fix -- fix f = f (fix f) fix = moeb id 

As you can see, moeb is a generalization of the fix function.

There are other functions that can be used as moeb parameters, such as traverse and foldMap , but I still don’t know why you can use it for something useful.