# News aggregator

### extensible-transformers

### Taking over setlocale

### Looking for architecture/infrastructure advice on coping with thousands of concurrent clients

### Danny Gratzer: Examining Hackage: logict

One of my oldest habits with programming is reading other people’s code. I’ve been doing it almost since I started programming. For the last two years that habit has been focused on Hackage. Today I was reading the source code to the “logic programming monad” provided by logict and wanted to blog about how I go about reading new Haskell code.

This time the code was pretty tiny, find . -name *.hs | xargs wc -l reveals two files with just under 400 lines of code! logict also only has two dependencies, base and the mtl, so there’s not a big worry of unfamiliar libraries.

Setting UpIt’s a lot easier to read this post if you have the source for logict on hand. To grab it, use cabal get. My setup is something like

~ $ cabal get logict ~ $ cd logict-0.6.0.2 ~/logict-0.6.0.2 $ cabal sandbox init ~/logict-0.6.0.2 $ cabal install --only-dependencies Poking AroundI’m somewhat ashamed to admit that I use pretty primitive tooling for exploring a new codebase, it’s grep and find all the way! If you use a fancy IDE, perhaps you can just skip this section and take a moment to sit back and feel high-tech.

First things first is to figure out what Haskell files are here. It can be different than what’s listed on Hackage since often libraries don’t export external files.

~/logict-0.6.0.2 $ find . -name *.hs ./dist/build/autogen/Paths_logict.hs ./Control/Monad/Logic.hs ./Control/Monad/Logic/Class.hsAlright, there’s two source file and one sitting in dist. The dist one is almost certainly just cabal auto-gened stuff that we don’t care about.

It also appears that there’s no src directory and every module is publicly exported! This means that we only have two modules to worry about.

The next thing to figure out is which to read first. In this case the choice is simple: greping for imports with

grep "import" -r Controlreveals that Control.Monad.Logic imports Control.Monad.Logic.Class so we start with *.Class.

Reading Control.Monad.Logic.ClassAlright! Now it’s actually time to start reading code.

The first thing that jumps out is the export list

module Control.Monad.Logic.Class (MonadLogic(..), reflect, lnot) whereAlright, so we’re exporting everything from a class MonadLogic, as well as two functions reflect and lnot. Let’s go figure out what MonadLogic is.

class (MonadPlus m) => MonadLogic m where msplit :: m a -> m (Maybe (a, m a)) interleave :: m a -> m a -> m a (>>-) :: m a -> (a -> m b) -> m b ifte :: m a -> (a -> m b) -> m b -> m b once :: m a -> m aThe fact that this depends on MonadPlus is pretty significant. Since most classes don’t require this I’m going to assume that it’s fairly key to either the implementation of some of these methods or to using them. Similar to how Monoid is critical to Writer.

The docs make it pretty clear what each member of this class does

msplit

Take a local computation and split it into it’s first result and another computation that computes the rest.

interleave

This is the key difference between MonadLogic and []. interleave gives fair choice between two computation. This means that every result that appears in finitely many applications of msplit for some a and b, will appear in finitely many applications of msplit to interleave a b.

>>-

>>- is similar to interleave. Consider some code like

(a >>= k) `mplus` (b >>= k)This is equivalent to mplus a b >>= k, but has different characteristics since >>= might never terminate. >>- is described as “considering both sides of the disjunction”.

I have absolutely no idea what that means.. hopefully it’ll be clearer once we look at some implementations.

ifte

This is the equivalent of Prolog’s soft cut. We poke a logical computation and if it

*can*succeed at all, then we feed it into the success computation, otherwise we’ll feed return the failure case.once

once is clever combinator to prevent backtracking. It will grab the first result from a computation, wrap it up and return it. This prevents backtracking further on the original computation.

Now the docs also state that everything is derivable from msplit. These implementations look like

interleave m1 m2 = msplit m1 >>= maybe m2 (\(a, m1') -> return a `mplus` interleave m2 m1') m >>- f = do (a, m') <- maybe mzero return =<< msplit m interleave (f a) (m' >>- f) ifte t th el = msplit t >>= maybe el (\(a,m) -> th a `mplus` (m >>= th)) once m = do (a, _) <- maybe mzero return =<< msplit m return aThe first thing I notice looking at interleave is that it kinda looks like

interleave' :: [a] -> [a] -> [a] interleave' (x:xs) ys = x : interleave' ys xs interleave _ ys = ysThis makes sense, since this will fairly split between xs and ys just like interleave is supposed to. Here msplit is like pattern matching, mplus is :, and we have to sprinkle some return in there for kicks and giggles.

Now about this mysterious >>-, the biggest difference is that each f a is interleaved, rather than mplus-ed. This should mean that it can be fairly split between our first result, f a and the rest of them m' >>- f. Now if we can do something like

(m >>- f) `interleave` (m' >>- f)Should have nice and fair behavior.

The next two are fairly clear, ifte splits it’s computation, and if it can it feeds the whole stinking thing return amplusm' to the success computation, otherwise it just returns the failure computation. Nothing stunning.

once is my favorite function. To prevent backtracking all we do is grab the first result and return it.

So that takes care of MonadTrans. The next thing to worry about are these two functions reflect and lnot.

reflect confirms my suspicion that the dual of msplit is mplus (return a) m'.

reflect :: MonadLogic m => Maybe (a, m a) -> m a reflect Nothing = mzero reflect (Just (a, m)) = return a `mplus` mThe next function lnot negates a logical computation. Now, this is a little misleading because the negated computation either produces one value, (), or is mzero and produces nothing. This is easily accomplished with ifte and once

lnot :: MonadLogic m => m a -> m () lnot m = ifte (once m) (const mzero) (return ())That takes care of most of this file. What’s left is a bunch of instances for monad transformers for MonadTrans. There’s nothing to interesting in them so I won’t talk about them here. It might be worth glancing at the code if you’re interested.

One slightly odd thing I’m noticing is that each class implements *all* the methods, rather than just msplit. This seems a bit odd.. I guess the default implementations are significantly slower? Perhaps some benchmarking is in order.

Now that we’ve finished with Control.Monad.Logic.Class, let’s move on to the main file.

Now we finally see the definition of LogicT

newtype LogicT m a = LogicT { unLogicT :: forall r. (a -> m r -> m r) -> m r -> m r }I have no idea how this works, but I’m guessing that this is a church version of [a] specialized to some m. Remember that the church version of [a] is

type CList a = forall r. (a -> r -> r) -> r -> rNow what’s interesting here is that the church version is strongly connected to how CPSed code works. We could than imagine that mplus works like cons for church lists and yields more and more results. But again, this is just speculation.

This suspicion is confirmed by the functions to extract values out of a LogicT computation

observeT :: Monad m => LogicT m a -> m a observeT lt = unLogicT lt (const . return) (fail "No answer.") observeAllT :: Monad m => LogicT m a -> m [a] observeAllT m = unLogicT m (liftM . (:)) (return []) observeManyT :: Monad m => Int -> LogicT m a -> m [a] observeManyT n m | n <= 0 = return [] | n == 1 = unLogicT m (\a _ -> return [a]) (return []) | otherwise = unLogicT (msplit m) sk (return []) where sk Nothing _ = return [] sk (Just (a, m')) _ = (a:) `liftM` observeManyT (n-1) m'observeT grabs the a from the success continuation and if no result is returned than it will evaluate fail "No Answer which looks like the failure continuation! Looks like out suspicion is confirmed, we’re dealing with monadic church lists or some other permutation of those buzzwords.

Somehow in a package partially designed by Oleg I’m not surprised to find continuations :)

observeAllT is quite similar, notice that we take advantage of the fact that r is universally quantified to instantiate it to a. This quantification is also used in observeManyT. This quantification also prevents any LogicT from taking advantage of the return type to do evil things with returning random values that happen to match the return type. This is what’s possible with ContT for example.

Now we have the standard specialization and smart constructor for the non-transformer version.

type Logic = LogicT Identity logic :: (forall r. (a -> r -> r) -> r -> r) -> Logic a logic f = LogicT $ \k -> Identity . f (\a -> runIdentity . k a . Identity) . runIdentityLook familiar? Now we can inject real church lists into a Logic computation. I suppose this shouldn’t be surprising since [a] functions like a slightly broken Logic a, without any sharing or soft cut.

Now we repeat all the observe* functions for Logic, I’ll omit these since they’re implementations are exactly as you’d expect and not interesting.

Next we have a few type class instances

instance Functor (LogicT f) where fmap f lt = LogicT $ \sk fk -> unLogicT lt (sk . f) fk instance Applicative (LogicT f) where pure a = LogicT $ \sk fk -> sk a fk f <*> a = LogicT $ \sk fk -> unLogicT f (\g fk' -> unLogicT a (sk . g) fk') fk instance Alternative (LogicT f) where empty = LogicT $ \_ fk -> fk f1 <|> f2 = LogicT $ \sk fk -> unLogicT f1 sk (unLogicT f2 sk fk) instance Monad (LogicT m) where return a = LogicT $ \sk fk -> sk a fk m >>= f = LogicT $ \sk fk -> unLogicT m (\a fk' -> unLogicT (f a) sk fk') fk fail _ = LogicT $ \_ fk -> fkIt helps for reading this if you expand sk to “success continuation” and fk to “fail computation”. Since we’re dealing with church lists I suppose you could also use cons and nil.

What’s particularly interesting to me here is that there are *no* constraints on m for these type class declarations! Let’s go through them one at a time.

Functor is usually pretty mechanical, and this is no exception. Here we just have to change a -> m r -> m r to b -> m r -> m r. This is trivial just by composing the success computation with f.

Applicative is similar. pure just lifts a value into the church equivalent of a singleton list, [a]. <*> is a little bit more meaty, we first unwrap f to it’s underlying function g, and composes it with out successes computation for a. Notice that this is very similar to how Cont works, continuation passing style is necessary with church representations.

Now return and fail are pretty straightforward. Though this is interesting because since pattern matching calls fail, we can just do something like

do Just a <- m Just b < n return $ a + bAnd we’ll run n and m until we get a Just value.

As for >>=, it’s implementation is very similar to <*>. We unwrap m and then feed the unwrapped a into f and run that with our success computations.

We’re only going to talk about one more instance for LogicT, MonadLogic, there are a few others but they’re mostly for MTL use and not too interesting.

instance (Monad m) => MonadLogic (LogicT m) where msplit m = lift $ unLogicT m ssk (return Nothing) where ssk a fk = return $ Just (a, (lift fk >>= reflect))We’re only implementing msplit here, which strikes me as a bit odd since we implemented everything before. We also actually need Monad m here so that we can use LogicT’s MonadTrans instance.

To split a LogicT, we run a special success computation and return Nothing if failure is ever called. Now there’s one more clever trick here, since we can choose what the r is in m r, we choose it to be Maybe (a, LogicT m a)! That way we can take the failure case, which essentially is just the tail of the list, and push it into reflect.

This confused me a bit so I wrote the equivalent version for church lists, where msplit is just uncons.

{-# LANGUAGE RankNTypes #-} newtype CList a = CList {runCList :: forall r. (a -> r -> r) -> r -> r} cons :: a -> CList a -> CList a cons a (CList list) = CList $ \cs nil -> cs a (list cs nil) nil :: CList a nil = CList $ \cons nil -> nil head :: CList a -> Maybe a head list = runCList list (const . Just) Nothing uncons :: CList a -> Maybe (a, CList a) uncons (CList list) = list skk Nothing where skk a rest = Just (a, maybe nil (uncurry cons) rest)Now it’s a bit clearer what’s going on, skk just pairs up the head of the list with the rest. However, since the tail of the list has the type m (Maybe (a, LogicT m a)), we lift it back into the LogicT monad and use reflect to smush it back into a good church list.

That about covers Control.Monad.Logic

Wrap UpI’ve never tried sharing these readings before so I hope you enjoyed it. If this receives some positive feedback I’ll do something similar with another package, I’m leaning towards extensible-effects.

If you’re interested in doing this yourself, I highly recommend it! I’ve learned a *lot* about practical engineering with Haskell, as well as really clever and elegant Haskell code.

One thing I’ve always enjoyed about the Haskell ecosystem is that some of the most interesting code is often quite easy to read given some time.

<script type="text/javascript"> /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */ var disqus_shortname = 'codeco'; // required: replace example with your forum shortname /* * * DON'T EDIT BELOW THIS LINE * * */ (function() { var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true; dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq); })(); </script> <noscript>Please enable JavaScript to view the comments powered by Disqus.</noscript> comments powered by Disqus### Why is package management so awful?

Upgrading ghc is extremely difficult. Upgrading cabal is extremely difficult. Cabal installing new packages almost always fails due to dependency version conflicts. I spent hours trying to download and compile yesod and hours with ghcjs. I'm still working on the latter. Are these issues being taken seriously in the haskell community? I'm quite surprised and honestly sad at how poorly haskell's dependency management was implemented given that everything else is architected so impressively. Is there hope? Because I would love to continue my path toward haskell enlightenment but *a lot* of my time is being wasted on installation issues.

[link] [97 comments]

### Storing functions with data-acid

Can acid-state be safely used with structures that cannot be checkpointed? In particular I was thinking of storing functions which can be updated. Then as long as I don't call createCheckpoint, things will continue to work?

So for example, something like -

data Func a b = Func { run :: a -> (b, (Func a b)) }I can then define a dummy safecopy instance -

instance SafeCopy (Func a b) where putCopy = undefined getCopy = undefinedDeclare a transaction -

apply :: a -> Update (Func a b) b apply a = do (b,f) <- gets (($ a) . run) put f return b $(makeAcidic ''Func ['apply])A sample function -

sample :: Func Int Int sample = sample' 0 sample' n = Func $ \a -> (a+n, sample' $ n+1)And then I can do this (I have tried this and it seems to work) -

main = do acid <- openLocalState sample putStrLn "Please enter an integer:" s <- getLine let n = read s n' <- update acid (Apply n) putStrLn $ "The answer is: " ++ (show n') submitted by haskman[link] [12 comments]

### Turning a message parser into a protocol handler

### ANNOUNCE: sai-shape-syb Generic mapping tohomogeneous types (etc.)

### security update practice?

### How to run SQL actions in persistent

### Travis CI

### Webdriver: Couldn't match type `Element' with `WDElement'

### Calkin-Wilf for Early(-ish) Haskellers

### Designing widgets in Reactive style

### The new haskell.org design

### Using Agda in Linux without emacs?

Hello, apologies if this question is irrelevant/doesn't belong here.

I've been reading a lot of agda tutorials for the past couple of days and almost all of them use emacs as an IDE (I might be wrong, but that's what it feels like). What I want to know is, can agda code be written separately and then afterwards be checked/compiled (again, not sure of the terminology) manually using commands in the terminal? I haven't been able to find much on the internet about this - any help at all would be very appreciated!

[link] [13 comments]