What else can `loeb` function be used for?

Yrogirg

I am trying to understand "Löb and möb: strange loops in Haskell", but right now the meaning is sleaping away from me, I just don't see why it could be useful. Just to recall function loeb is defined as

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

or equivalently:

loeb x = go 
  where go = fmap (\z -> z go) x

In the article there is an example with [] functor and spreadsheets implementation, but it is bit foreign for me just as spreadsheets themselves (never used them).

While I'm understanding that spreadsheet thing, I think it would help a lot for me and others to have more examples, despite lists. Is there any application for loeb for Maybe or other functors?

J. Abrahamson

The primary source (I think) for loeb is Dan Piponi's blog, A Neighborhood of Infinity. There he explains the whole concept in greater detail. I'll replicate a little bit of that as an answer and add some examples.

loeb implements a strange kind of lazy recursion

loeb :: Functor a => a (a x -> x) -> a x
loeb x = fmap (\a -> a (loeb x)) x

Let's imagine we have a type a, where Functor a, and an a-algebra (a function of type a x -> x). You might think of this as a way of computing a value from a structure of values. For instance, here are a few []-algebras:

length                ::          [Int] -> Int
(!! 3)                ::          [a]   -> a
const 3               :: Num a => [a]   -> a
\l -> l !! 2 + l !! 3 :: Num a => [a]   -> a

We can see that these a-algebras can use both values stored in the Functor and the structure of the Functor itself.

Another way to think of d :: a x -> x is as a value of x which requires some context–a whole Functorized value a x–in order to be computed. Perhaps this interpretation is more clearly written as Reader (a x) x, emphasizing that this is just a value of x which is delayed, awaiting the a x context to be produced.

type Delay q x = q -> x

Using these ideas we can describe loeb as follows. We're given a f-structure containing some Delayed values, where f is a Functor

Functor f, f (Delay q x)

Naturally, if we were given a q then we could convert this into a not delayed form. In fact, there's only one (non-cheating) function that does this polymorphically:

force :: Functor f => f (Delay q x) -> q -> f x
force f q = fmap ($ q) f

What loeb does is handle the extra tricky case where q is actually force f q, the very result of this function. If you're familiar with fix, this is exactly how we can produce this result.

loeb :: Functor a => a (Delay (a x) x) -> a x
loeb f = fix (force f)

So to make an example, we simply must build a structure containing Delayed values. One natural example of this is to use the list examples from before

> loeb [ length                  :: [Int] -> Int
       , const 3                 :: [Int] -> Int
       , const 5                 :: [Int] -> Int
       , (!! 2)                  :: [Int] -> Int
       , (\l -> l !! 2 + l !! 3) :: [Int] -> Int
       ]
[5, 3, 5, 5, 10]

Here we can see that the list is full of values delayed waiting on the result of evaluating the list. This computation can proceed exactly because there are no loops in data dependency, so the whole thing can just be determined lazily. For instance, const 3 and const 5 are both immediately available as values. length requires that we know the length of the list but none of the values contained so it also proceeds immediately on our fixed-length list. The interesting ones are the values delayed waiting on other values from inside our result list, but since (!! 2) only ends up depending on the third value of the result list, which is determined by const 5 and thus can be immediately available, the computation moves forward. The same idea happens with (\l -> l !! 2 + l !! 3).


So there you have it: loeb completes this strange kind of delayed value recursion. We can use it on any kind of Functor, though. All we need to do is to think of some useful Delayed values.


Chris Kuklewicz's comment notes that there's not a lot you could do interestingly with Maybe as your functor. That's because all of the delayed values over Maybe take the form

maybe (default :: a) (f :: a -> a) :: Maybe a -> a

and all of the interesting values of Maybe (Delay (Maybe a) a) ought to be Just (maybe default f) since loeb Nothing = Nothing. So at the end of the day, the default value never even gets used---we always just have that

loeb (Just (maybe default f)) == fix f

so we may as well write that directly.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

What else can php Classes be used for?

From Dev

What character can be used in a SCSS/SASS function and variable name?

From Dev

What can `inxi` be used for?

From Dev

What can `inxi` be used for?

From Dev

Can a function be used in a equation

From Dev

What is the relationship() function used for in SQLAlchemy

From Dev

What is the function of -'a' when used with an array

From Dev

What is the relationship() function used for in SQLAlchemy

From Dev

What can JSON strings be used for?

From Dev

On what level can SPDY be used?

From Dev

What can be used to 'gzip' in Windows?

From Dev

What is OpenStack? And how can it be used?

From Dev

What can be used for Webcommunication on Android

From Dev

In what cases mongoexport can be used?

From Dev

What is a name of this port? And for what purpose can it be used?

From Dev

When embedding CLIPS into C Language, what function can used to modify the fact from C program

From Dev

When embedding CLIPS into C Language, what function can used to modify the fact from C program

From Dev

What design pattern should be used when similarly if-else grows?

From Dev

What is the XsrfKey used for and should I set the XsrfId to something else?

From Dev

Is Office Fabric used in creating the Exchange Admin Center? What else is?

From Dev

What else can a django view be made of?

From Dev

What else I can do to optimise this query?

From Dev

Vowpal Wabbit: What hash function is used exactly?

From Dev

What's the highest order function used in practice?

From Dev

What is 'typeof define === 'function' && define['amd']' used for?

From Dev

What is the initialState used for in Redux createStore function

From Dev

What is the difference between qDebug() used as a stream and as a function

From Dev

what is the map/flatmap function used in for comprehensions?

From Dev

What does "this" do when used in function brackets?

Related Related

  1. 1

    What else can php Classes be used for?

  2. 2

    What character can be used in a SCSS/SASS function and variable name?

  3. 3

    What can `inxi` be used for?

  4. 4

    What can `inxi` be used for?

  5. 5

    Can a function be used in a equation

  6. 6

    What is the relationship() function used for in SQLAlchemy

  7. 7

    What is the function of -'a' when used with an array

  8. 8

    What is the relationship() function used for in SQLAlchemy

  9. 9

    What can JSON strings be used for?

  10. 10

    On what level can SPDY be used?

  11. 11

    What can be used to 'gzip' in Windows?

  12. 12

    What is OpenStack? And how can it be used?

  13. 13

    What can be used for Webcommunication on Android

  14. 14

    In what cases mongoexport can be used?

  15. 15

    What is a name of this port? And for what purpose can it be used?

  16. 16

    When embedding CLIPS into C Language, what function can used to modify the fact from C program

  17. 17

    When embedding CLIPS into C Language, what function can used to modify the fact from C program

  18. 18

    What design pattern should be used when similarly if-else grows?

  19. 19

    What is the XsrfKey used for and should I set the XsrfId to something else?

  20. 20

    Is Office Fabric used in creating the Exchange Admin Center? What else is?

  21. 21

    What else can a django view be made of?

  22. 22

    What else I can do to optimise this query?

  23. 23

    Vowpal Wabbit: What hash function is used exactly?

  24. 24

    What's the highest order function used in practice?

  25. 25

    What is 'typeof define === 'function' && define['amd']' used for?

  26. 26

    What is the initialState used for in Redux createStore function

  27. 27

    What is the difference between qDebug() used as a stream and as a function

  28. 28

    what is the map/flatmap function used in for comprehensions?

  29. 29

    What does "this" do when used in function brackets?

HotTag

Archive