I have been doing some python brush-up over the last couple of days, and came across the following bit of code in an irc chat about approaches for fibonacci in python.

def fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return a
print fib(1000)

I think this is pretty typical, reasonable, and efficient python code.

I wondered, how would I express this in haskell? How different this computation looks from the canonical

fibs = 1:1:zipwith (+) fibs (tail fibs)


The answer, as is commonly the case for code written in imperative languages, is that this algorithm lives in the state monad. It can be ported to haskell, practically transliterated, as:

import Control.Monad.State
-- haskell translational of python algo
def fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return a
print fib(1000)
fib :: Integer -> Integer
fib n = flip evalState (0,1) $ do
  forM (xrange n) $ \_ -> do
    (a,b) <- get
    put (b,a+b)
  (a,b) <- get
  return a 

xrange n = [0..(n-1)]

-- test that it works
traditionalFibs' = 1: 1: (zipWith (+) traditionalFibs' (tail traditionalFibs'))
traditionalFib n = traditionalFibs' !! (n-1)

t = fib 1000 == traditionalFib 1000

Also added this to hawiki at



Patch-Tag is getting closer to a place where I’d feel comfortable charging for it, but there are a couple of things I need to take care of first.

First, I want to be more confident that I can scale this service out if I start getting a lot more users. It needs to be rock solid. No more downtime, no more crashes. This will definitely involve code tweaks for places that use unjustifiably large amounts lot of memory, and may (or may not — haven’t decided yet) mean infrastructure changes.

Second, Patch Tag already does backups but I am going to revisit this process one more time to convince myself that this is as rock solid as it can get.

Happy belated thanksgiving everyone. There will be some more interesting news soon, I am feeling sure!

I’m keeping this one brief… Matt Elder has decided that it’s time to move on from patch-tag, in order to focus on other projects and the new addition to his family.

Thanks for all the good work, Matt. Patch-tag wouldn’t have
gotten this far without you.

I am in the process of migrating patch-tag to the latest version of happstack, and I thought I would post some diffs to aid others who have the same task.

This probably isn’t of much interest unless you are actually faced with a migration — but if you are, could save you some time and starting at compile complaints.

<                       happstack-data == 0.1,
<                       happstack-helpers == 0.11,
<                       happstack-ixset == 0.1,
<                       happstack-server == 0.1,
<                       happstack-state == 0.1,
<                       happstack-util == 0.1,
>                       happstack-data == 0.3.3,
>                       happstack-helpers == 0.30,
>                       happstack-ixset == 0.3.2,
>                       happstack-server == 0.3.3,
>                       happstack-state == 0.3.3,
>                       happstack-util == 0.3.2,

notice msum

< controller pubdom privdom ts dynamicTemplateReload realEmail wikitmpl mime useGoogAnalytics = 
<    (staticfiles ++)
> controller pubdom privdom ts dynamicTemplateReload realEmail wikitmpl mime useGoogAnalytics = 
>     msum [ staticfiles

notice ReaderT

< mainController pubdom privdom ts' dynamicTemplateReload realEmail wikitmpl mime ga = 
<        [ ServerPartT $ \rq -> do
> mainController pubdom privdom ts' dynamicTemplateReload realEmail wikitmpl mime ga = 
>        ServerPartT $ ReaderT $ \rq -> do

notice s/unserverPartT/runServerPartT/

<   unServerPartT ( multi $ mainCommon pubdom privdom (RenderGlobals rq ts mbSession ga) mailFx wikitmpl mime) rq
<   ] 
>   runServerPartT ( msum $ mainCommon pubdom privdom (RenderGlobals rq ts mbSession ga) mailFx wikitmpl mime) rq



To get the most out of the following blog post, first try writing your partition function, which does the same thing as Data.List.partition.

*Partition> partition even [1..10]

Then write a testing function, tpf, which checks your partition function against a variety of input, including large or infinite input. (Which means we don’t just use quickcheck).

Then read the blog post to see what obstacles I hit when I went through this process.

source here if you’re irked by wordpress aggressively cutting off the right side of the page.

{-# LANGUAGE NoMonomorphismRestriction #-}
module Partition where
import Debug.Trace.Helpers
import qualified Data.List as DL
import Debug.Trace

-- first attempt
partition f [] = ([],[])
partition f (x:xs) = 
  let (as,bs) = partition f xs
  in  if (f x) then (x:as,bs) else (as,x:bs)
t1 = tpf partition 

-- testing function.
tpf partif = 
      let a = last . snd . partif even $ [1..(10^6)]
          b = head . snd . partif even $ [1,2..] 
          c = last . snd . partif even $ [1..(10^8)] 
       in (a,b,c)

-- sanity checks / benchmarks. our own code should be at least as fast as Data.List versions.
-- a is immediate, b is immediate, c takes about 10 seconds. 
tDL = tpf DL.partition

-- a test and b test are fine but that 10^8 list seems to take forever. 
-- let's think about this. What algorithm are we using?
-- Actually, I don't know the answer to that.
-- but looking at that let/in, I don't have a clear sense of crunching through a list and building up a result, which is usually the ideal. 
-- So let's try this with a fold.

-- Next question, what kind of fold?
-- Easy answer: just try both and see what happens! 
-- Once you've written one, you have the other just by flipping the arguments in the helper function :)
-- (Note: for the foldl, we try strict foldl' by default, as there is usually no reason to use lazy foldl:  
-- http://haskell.org/haskellwiki/Foldr_Foldl_Foldl'
partitionR f xs = foldr g ([],[]) xs
  where g next accum@(as,bs) = if f next then (next:as,bs) else (as,next:bs)
partitionL' f xs = DL.foldl' g ([],[]) $ reverse xs
  where g accum@(as,bs) next = if f next then (next:as,bs) else (as,next:bs)
-- Harder answer, which requires thought: we probably want a foldr here, because the b test uses an infinite list and a strict fold
-- won't return anything if you feed it an infinite list.

-- OK, let's try foldr
t2 = tpf partitionR -- result: immediate stack overflow on the a test, and if you try them separately, it overflows all 3 tests.
                    -- that's kind of sad.

-- for no particular reason, let's try a strict foldl version (warning! be careful running this!)
t3 = tpf partitionL'
  -- at least the a test succeeds after a few seconds, confirming the intuition that strict foldl' crunches through a list
  -- and returns output after it's done.
  -- the b test exhausts computer memory, eventually the fan starts whirring louder than I can think, mouse stops responding and have to reboot
  -- so like I said, careful running this, and hit control c!

--okay, I give up, let's peek at the standard libs (SL) Data.List
-- this isn't word for word what the ghc standard libs Data.List has, so as to be more similar to the functions we wrote so far, 
-- but it's the same algo, and same performance.
-- the important difference is the lazy match
partitionSL p xs = foldr g ([],[]) xs 
  where g next accum = if (p next) then (next:fst accum,snd accum) else (fst accum, next:snd accum) 
        -- which is the same as below, using irrefutable pattern syntax:  
        -- g next ~accum@(as,bs) = if (p next) then (next:as,bs) else (as, next:bs) 
-- Sure enough, same performance as Data.List.Partition
-- Note: to get the same performance as lazy list, you need to compile the module before loading in ghci, eg
-- ghc --make PartitionM.hs, then ghci PartitionM
-- if you do ghci PartitionM.hs, this doesn't terminate (at least, not in under a minute I'm an impatient guy.)
tSL = tpf partitionSL

-- So, why does partition need an irrefutable pattern in the accum argument?
-- Let's look at the original right folded partition again, rewritten as follows, for a 3 element list

partitionR2 f xs = foldr (select f) ([],[]) xs
select f next accum@(as,bs) = if f next then (next:as,bs) else (as,next:bs)
-- select' g next accum = if (p next) then (next:fst accum,snd accum) else (fst accum, next:snd accum) 

tpr2 :: ([Int],[Int])
tpr2 = partitionR even [1..3]
tpr2a = 1 `g` ( 2 `g` ( 3 `g` ([],[]) ) )
g = select even

-- when the accum argument to select is a strict pattern match, the algorithm can't proceed past the first element
-- without evaluating everything inside the first set of parenthesis. 
-- For a million element list, this is going to be a problem.
-- if the accum arg is lazy (just accum without the @ binding), the algorithm can proceed to the if test,
-- calculate the tuple with the list parts as just a thunk to be evaluabed later, and keep chugging along,
-- by calculating the list parts next.

It is said that in haskell, If it Compiles, It Works.

This is true, but what do you do when it won’t compile?

I came across a real world scenario for this just now, when I was in the process of removing the HStringTemplateHelpers dependency from happs tutorial. The reason for this is that HStringTemplateHelpers uses the unix package (indirectly, via FileManip), which means that at the present time happs tut won’t run on windows, which lately has me smacking myself like dobby the masochistic house elf in the harry potter movies.*

The dependency wasn’t in one file, but scattered throughout the code. Some places, the dependency wasn’t that important, I could just comment the function out, but in other cases the function was core to the app and commenting it out caused cascading compile failures. Doing the type/function arithmetic in my head for figuring out what depended on what was giving me a headache and tempting me to veg out on youtube rather than face the problem, always a warning sign for me that I’m doing something wrong.

I needed to make my program compile, just so I could think about it with my head screwed on straight.

So, instead of commenting out the HStringTemplateHelpers-dependent functions, I set them equal to undefined and commented out their type signatures (since the type sig might be using a type that was defined in the dependency.

-- paintProfile :: RenderGlobals -> String -> UserProfile -> String -> String
paintProfile rglobs user cp userimagepath = undefined {-.....-}

A few comment-outs later and cabal install compiles! Of course, if I actually try running the resulting binary, I will hit an undefined error right away, but the point is that I can think again, and start rewriting my offending functions in a methodical way until there are no more undefineds, which is easly checked with

grep -irn undefined src

For what it’s worth, I could have also used

paintProfile rglobs user cp userimagepath = error "paintProfile uses HStringTemplateHelpers... bad dobby! bad dobby! Dobby will have to shut his ears in the oven door for this."

But whatever :)

* I suppose the righter thing to do would be to fix FileManip, but I am choosing the easy way out just to get it done. Eventually I woud like to move away from HStringTemplate with happs and use mostly Text.XHTML and/or HSP, which is type safe, which HSTringTemplate just thrown in for convenience and newb friendliness.

I wanted to have a look at the latest happstack release, and noticed the documentation still wasn’t available on haddock.


It wasn’t available locally either, when I did cabal install happstack-server. In fact, haddock was not available offline for anything.

To get the haddocks locally, I edited ~/.cabal/config, setting

Documentation: True

(and uncommenting that line by removing the starting –)

After this, cabal install –reinstall built the documentation in


handy :)

But shouldn’t this flag be on by default?


cabal haddock –hyperlink-source

installs documentation with links to source code, which imho should also be on by defualt.

cabal install –haddock-options=–hyperlink sourceblehblehbleh

doesn’t throw an error. without the blehblehbleh it runs, but doesn’t install with source links, which seems like a bug to me.


Get every new post delivered to your Inbox.