the Patch-Tag blog

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

 </code></pre>

 

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]
([2,4,6,8,10],[1,3,5,7,9])

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.

http://hackage.haskell.org/package/happstack

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

.cabal/share/doc/happstack-server-0.3.3/html/

handy

But shouldn’t this flag be on by default?

UPDATE:

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.

Patch-Tag now writes the _darcs/prefs/email file for repositories with the owner’s email.

That means if you check out a public repo (without being a member with write access to shared) you can contribute patches back to the repo creator simply with the command

darcs send

This assumes you have sendmail configured for sending email from the command line. But if you don’t, no problem, you can output to a file and send as attachment. Every repo has instructions that will hopefully make this easy for newbies, for example one of mine.

Thanks for the users who suggested implementing this feature, now that it’s there it seemed obvious all along.

Enjoy

Hey everybody.

I am once more without day job, and so patch-tag is getting more attention than it is used to. Could patch-tag be a day job, after all? Let’s just say I am toying with this idea but trying to stay grounded too. I don’t have as many users as I wanted when I started this project — not by a long shot. However, a good proportion of the users I do have seem to be “real” users — actually using repos, browsing around, not just signing up and moseying away when the novelty wears off. This is good. On the other hand, I worry that the logs I am basing this on might not be fair — perhaps bots or other phenomena are responsible for the apparent signs of activity. So, this — understanding true usage — is also something I am working on.

This week was mostly incremental improvements, but it was all stuff that has to happen before shooting for bigger goals (gitit, git format repos, and todo lists).

• Edit profile page improvements: you can change your primary email, delete profile, etc
• The repo command page has a “push patches over email: ” section.
• Added some admin functionality, for better understanding my user base, and in preparation to pull the trigger on paid repos at some time in the not too distant future
• Refactored and cleaned up a lot of code. Hey, is that a feature? Maybe not for you… but it’s a feature for me, the guy that has to deal with self-created mess.

I am also working on a talk to evangelize happstack to the southern california FP and web dev community sometime in the next few weeks.

Stay cool, and keep tagging.

A wise haskell hacker said you don’t need to understand monads to use em, and this I find to be mostly true.

You don’t need to understand category theory either.

Lately though, I’ve been trying to deepen my intuition a bit anyway.

This is something I wrote lately that I keep revisiting when thinking about monadic machinery: specificaly the bind, left bind, join and return operators, as well as the pure and fmap operators used with Applicative and Functor.

How do these funny named operators fit together and what are they good for?

Concrete examples help, and for now my concrete example is the list monad. Pure and return do the same thing, since the list monad is also an applicative functor: just :[], put in a list. Fmap is, of course, map. I find myself using left bind more often than bind in my code, and in the list monad left bind is concatMap. Oh, and join is concat. You don’t hear about join much, but it turns out to be important when understanding monads categorically. Join takes m (m a) -> m (a), ie two monad nestings deep to one. Mysterious, eh?

If any of this rang a bell and you have been scratching your head for a simple bit of code you can stare at and play around with in your head, you may enjoy this.

To start with, try out f1 xs, f2 xs, f3 xs, u1 xs, u2 xs in ghci, just to see what’s giong on. Then… well, just read the code for suggestions about how to learn from it.

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Applicative
import Control.Monad
import Test.QuickCheck

-- inspired by mixing monads, arrows, and applicative functors
-- http://yumagene.livejournal.com/2245.html
--  http://www.sfu.ca/~ylitus/courses/cmpt481731/slides/FPjul9.pdf

-- An interesting thing for learning you can do in your head:
-- replace (=<<), (<$>), and join with the list equivalents, after staring at this for a while.
-- The equivalents:
--   (=<<): concatMap
--   (<$>): map
--   join: concat
-- doing that helped me understand monad/functor machinery better.

-- a list of lists, to illustrate "burrowing in" two levels with (<$>) . (<$>) and other machinery
xs :: [[Integer]]
xs = [[2,4,6],[7..13],[10,20..50]] 

t = sequence_ [tflattened, tunflattened]

infs = repeat [1,2,3] -- the f functions produce output fine with infinite lists as well.

-- you lose the "list of lists" structure, because (=<<)/join are flattening
f1 els = (=<<) ((<$>) (* 3)) $ els
f2 els = join . ((<$>) $ (<$>) (* 3)) $ els
f3 els = join . (((<$>) . (<$>)) (*3)) $ els -- same thing, note the burrowing in two levels thing.
tflattened = quickCheck p
  where p :: [[Integer]] -> Bool
        p xs = (f1 xs) == (f2 xs) && (f1 xs) == (f3 xs)

-- if you want to preserve the list of lists structure, compose your monadic function with (pure .) behind it.
u1 els = (=<<) (pure . (<$>) (* 3)) els
u2 els = join . ((pure . (<$>) (* 3)) <$>) $ els

tunflattened = quickCheck p
  where p :: [[Integer]] -> Bool
        p xs = u1 xs == u2 xs

--flatten=join

-- Questions/Lessons Learned: 

-- Q0: are f1 and f2, and u1 and u2 the same function?
-- by same I mean
-- a) produce the same output for the same input everywhere (appears to be true for list monad)
-- b) computed the same way, one is not more efficient than the other
-- Answer to Q0: yes, pretty much.

-- Q1. what is the relationship between bind and join?
-- A. -- (=<<) f mx = join . (f <$>)  $ mx -- bind could have been defined this way, though in practice it's not.
  --  translation : -- functor map your monad function over the monad value (<$> f)
                    -- and pop one level of structure (join)
                    -- in a list, (=<<) f is concat . (map f)
-- Q. can this be proved using monad/functor/applicative laws or similar?
-- A. not proved exactly, but more like trivially true assuming the monad laws hold for your structure, which they should.
--   (Monad laws should be proven separately for each structure you define a monad laws. They *are* proven for list, maybe, maybe others.
-- Q. does ((<$>) . (<$>)) have some interesting roles in reasoning about monads or applicatives?
-- A. Burrow in two levels before applying the function.

-- (=<<) is concatMap in list context. join is concat in list context.

Patch-Tag has upgraded to darc 2.3.1.

I have also started logging darcs actions to see which ones take the longest in hopes of providing the development cabal with intelligence for some hard to squash bugs.

Patch-Taggers, I am about to pull the trigger on namespaced repos.

That means that repo paths will look like

http://patch-tag.com/r/myuser/myrepo

rather than (current)

http://patch-tag.com/r/myrepo

This is nice if you want to branch someone else’s repo, no need to call it repo_vxxx or however people have been doing it.

This breaks public repo urls, however. After this feature goes live

http://patch-tag.com/r/myrepo

will give you a search of all repos created by any user which match that name.

Private repo urls checkouts *should* continue to work with a symlink, but if there is any problem please go to the repo home page and look at the

I expect this feature will go live sometime in the next few hours, and I will update again after I pull the trigger.

Update: Site is down while migration in progress.

Update: Site is up again. Looks like private repo url checkouts do not work with symlink as I had hoped. I’ll look into this tomorrow.

If anything else appears to not be working please email me or notify the patch-tag-users google group.

Thanks for your patience, and I hope you enjoy namespaces!

Hey taggers, I have stopped being a full time entrepreneur and got a job with a startup that pays the bills: scaling and automations engineer with modernfeed.com, which is being rebranded under a domain which I must not name, at least for the next six weeks.

Confession time: I have not done a lot for patch tag the last two months, other than think and answer emails. (Well, I did a few tweaks to gitit and filestore, which will hopefully pay off eventually here.)

Two months ago is when I decided, I Must Get Paid, and monetizing patch tag was going to take longer than I could wait. Month 1 (June) I spent mainly in new york trying to cobble together a startup that merited enough VC money to live on, with a team that could do it full time. I felt like a scrappy screenplay writer on the mean streets of hollywood (except this was new york) pitching to producer after producer, living in a basement while I reached for my dreams, wheeling and dealing… except that this didn’t have a hollywood ending… I just kind of lost steam and said, enh.

Month 2 (July) I spent hunting for a paying job, bouncing between chicago, san francisco and L.A.

Funny thing, now I actually DO work in hollywood!

Now that I am gainfully employed again, I hope that I will actually be able to start investing some energy into patch tag again, on nights and weekends.

From what I hear, the baby that has been keeping up the other half of the partnership may be approaching the end of the “cry all night” stage as well.

So, we shall see!