4 ms·
It's not really comparable, but minimalistic spreadsheet applications always remind me of Dan Piponi's Haskell `loeb` function [0]---a "one-line" "spreadsheet"
by tel 13y ago
It's not really comparable, but minimalistic spreadsheet applications always remind me of Dan Piponi's Haskell `loeb` function [0]---a "one-line" "spreadsheet" "implementation".
The blog post is very interesting to read, but here's the meat. We're looking for a function with type
loeb :: Functor f => f (f a -> a) -> f a
and without thinking about the meaning of it, we can implement it as
loeb x = fmap (\a -> a (loeb x)) x
which embodies a certain, strange kind of recursion. It turns out that it's "spreadsheet recursion". We build a list of functions from lists of a to a like
test :: [[Int] -> Int]
test = [ (!! 1), length, (!! 0) ] -- think [A1, length(A), A0]
then `loeb test` "completes" the list by applying the "result list" to each of the functions of the source list.
loeb test == [3, 3, 3]
Laziness lets the recursion proceed despite "evaluating" the list from left to right. Infinite loops still fail
loeb [(!! 0)] == [............ waiting
It's also interesting to think of how to do "spreadsheet recursion" on exotic data types like trees.
data Binary a = Branch (Binary a) a (Binary a) | Tip
deriving (Show, Functor)
depth Tip = 0
depth (Branch l _ r) = succ (max (depth l) (depth r))
top default Tip = default
top _ (Branch _ a _) = a
> loeb (Branch Tip depth (Branch Tip (top 0) Tip))
Branch Tip 2 (Branch Tip 2 Tip)
[0] http://blog.sigfpe.com/2006/11/from-l-theorem-to-spreadsheet.html http://blog.sigfpe.com/2006/11/from-l-theorem-to-spreadsheet...
- aufreak3 13y agoWas about to post this as well. By far the neatest application of curry-howard i've stumbled on.
- idProQuo 13y agoJust yesterday I was about to temporarily quit Haskell after slamming my face into Learn You A Haskell's Functor chapter. But after seeing the concept applied (jokes for nerds!) like this, I think I'm going to give it another shot. Thanks!
- tel 13y agoIf you're ever in need of more motivation, be sure to take a look at more posts on Neighborhood of Infinity. It's truly an inspiring blog!
- tel 13y agoOne 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.
- tel 13y agoAnd 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)
- chrisdone 13y agoHere's a solution to the Twitter waterflow problem with loeb: http://chrisdone.com/posts/twitter-problem-loeb http://chrisdone.com/posts/twitter-problem-loeb