# Day 8: LogicT — A List Transformer

The list monad lets you perform non-deterministic searches for a solution to a problem. At each step of your program, you can provide a choice of possible values to bind to a variable, and the rest of the program will run several times, trying each possible value and collecting all the results from every run into one thing. That is what `>>=` is for in `[]`.

Here’s a pretty contrived problem: we’re going to search all of the integers to see if there is an integer greater than 100.

First we need a list of all the integers, which we’ll get by combining the positives, zero and the negatives.

`positives = [1..]negatives = map (* (-1)) [1..]the_numbers = positives ++ [0] ++ negatives`

Now we can run a simple program to find the first ( `head` ) solution:

`a_solution = head \$ do  n <- the_numbers  guard (n > 100)  return n`

We’ll go over all of the integers, and for each one, if it matches our search condition, we’ll return it, or otherwise we’ll abort this part of the search with no results.

`> a_solution101`

Let’s use the same technique to search for an integer less than 0. Can you think of such an integer? Hopefully. Here’s the program, just modified a little bit with our new condition:

`a_solution = head \$ do  n <- the_numbers  guard (n < 0)  return n`

Alas, it hangs rather than giving an answer:

`> a_solution...infinite wait...`

This program checks `the_numbers` in order, and we defined it using `++` as first having all the (infinite number of) positive numbers, then 0, then the (infinite number of negatives). We won’t ever consider any negative numbers as possible solutions until we’ve checked all the positive numbers. `++` is unfairly favouring the left hand side over the right hand side.

#### Fairer Disjunction

How about we use `interleave` instead of `++` ?

`> the_numbers = positives `interleave` [0] `interleave` negatives> take 10 the_numbers[1,-1,0,-2,2,-3,3,-4,4,-5]`

We’ve lost some of the ordering that we had before: our three lists are now all jumbled up with each other. But that means our search program will find a solution (on the second attempt, even).

Lots of monads have a transfomer version (sometimes, even, the basic version in terms of the transformer and `Identity`) — is there is sensible one for `[]`? So that we can get (for example) `ListT IO` which would act sometimes like a list and sometimes like `IO`.

Each step in `ListT IO` could run an IO action that returns many values, and the rest of the program will be run for each of those. Similarly, there could be `mplus` that works like `++` but on `ListT IO` actions.

A very simple implementation says a `ListT IO a` action is an embedded `IO [a]` action which runs and returns a list, and have `>>=` and `mplus` that work as in a regular list.

Like the earlier pure example, this works badly in the case of infinite lists: if the `IO` action that produces a list runs forever (producing values as it goes), the next step of the program is not even attempted once! The action needs to finish before it can return even the start of the result list — we’re far too strict in the first step.

A related problem arises if we try the “`interleave` instead of `++`” trick — we would need our three IO actions producing the three parts to have run for infinitely long before we can make the first test. Not only would we not find any negative answers, we wouldn’t find any positive ones either.

#### LogicT to the rescue

This, broadly, is what `LogicT` sets out to do. It introduces a new primitive, `msplit`, with roughly this type signature: (very simplified)

`msplit :: LogicT m a => LogicT m (Maybe (a, LogicT m a))`

This works a little bit like a `case` match on a list: given a pure list, you can case match and get either the empty list or a pair: the first element of the list, and the rest of the list.

Given a `LogicT m` action `a`, running`msplit a` will either give you `Nothing` (like the empty list), or an element and a new action — analogous to the first element and (an action that will provide) the rest of the list. It will run the action for long enough to produce a single element, and then return control back to you.

Now an `interleave` can be defined which takes elements alternately from two `LogicT` actions and returns them interspersed with each other, without needing either of the supplied actions to fully complete — each one only gets to run long enough to produce one answer before the other one gets a chance. Here’s some pseudo-code based on the LogicT paper listed at the bottom:

`interleave :: LogicT m a -> LogicT m a -> LogicT m ainterleave l r = do  s <- msplit l  case s of    Nothing -> r  -- we've reached the end of l so all that                  -- remains is r    Just (s, rest) -> return s `mplus` interleave r rest       -- we got a value, so return it, and then interleave       -- the rest, starting with r first`

There is a pile of other interesting stuff that `msplit` facilitates, covered in section 3 of the paper listed at the bottom — for example a fair version of `>>=` (did you know it wasn’t fair?) and some search pruning operations.