Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

One more cool trick from the same article (slightly modified). It's a factorial function computed on an "infinite spreadsheet". But how?

    fact = loeb fact' where
      fact' 0 _ = 1
      fact' n f = n*f (n-1)
If we ask GHC for the type of `fact'` then we see that it is

    Int -> ((Int -> Int) -> Int)
which we can interpret via the `Reader Int` monad as being

    m (m Int -> Int)
    -- for 
    m a = (Int -> a)
Now, `f :: (Int -> a)` as a functor is isomorphic to an infinite stream

    map f [0, 1, ...]
if we ignore the negative numbers. So we can think of `fact'` as having the type

    Stream (Stream Int -> Int)
where each function in the stream takes its own index and multiplies it by the value at the previous index.

Then `loeb` completes the computation using spreadsheet recursion.



And because I just find this really fascinating, here's a more direct implementation of `fact`

    data Stream a = Stream a (Stream a)
                    deriving Functor

    tabulate :: (Int -> a) -> Stream a
    tabulate f = go 0 where
      go n = Stream (f n) (go (succ n))

    index :: Stream a -> (Int -> a)
    index (Stream a _)  0 = a
    index (Stream a st) n = index st (pred n)

    -- btw: tabulate . index == id
    -- and  index . tabulate == id

    fact :: Int -> Int
    fact n = index (loeb facts) n where
      facts :: Stream (Stream Int -> Int)
      facts = tabulate $ \i stream -> i * index stream (i-1)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: