Typed Logic

Monads in Java

2011-09-25T19:22:00.000-07:00

A while back Brent Yorgey http://byorgey.wordpress.com posted a menagerie of types. A very nice survey of types in Haskell, including, among other things, the monadic types.

A reader posted a question, framed with 'you know, it'd be a lot easier for me to understand monads if you provided an implementation in Java.'[1]

Well, that reader really shouldn't have done that.

Really.

Because it got me to thinking, and dangerous things comes out of geophf's thoughts ... like monads in Java.

Let's do this.

Problem Statement

Of course, you just don't write monads for Java. You need some motivation. What's my motivation?

Well, I kept running up against the Null Object pattern, because I kept running up against null in the Java runtime, because there's a whole lot of optionality in the data sets I'm dealing with, and instead of using the Null Object, null is used to represent absence.

Good choice?

Well, it's expedient, and that's about the best I can say for that.

So I had to keep writing the Null Object pattern for each of these optional element types I encountered.

I encounter quite a few of them ... 2,100 of them and counting.

So I generalized the Null object pattern using generic types, and that worked fine ...

But I kept looking at the pattern. The generalization of the Null Object pattern is Nothing, and a present instance is Just that something.

I had implemented non-monadic Maybe.

And the problem with that is that none of the power of Maybe, as a Monad, is available to a generalized Null Object pattern.

Put another way: I wish to do something given that something is present.

Put another-another way: bind.

So, after a long hard look ('do I really want to implement monads? Can't I just settle for 'good enough' ... that really isn't good enough?), I buckled down to do the work of implementing not just Maybe (heh: 'Just Maybe'), but Monad itself.

Did it pay off? Yes, but wait and see. First the implementation. But even before that, let's review what a monad is.

What the Hell is a Monad?

Everybody seems to ask this question when first encountering monads, and everybody seems to come up with their own explanations, so we have tutorials that explain Monads as things as far-ranging from spacesuits to burritos.

My own explanation is to punt ... to category theory.

A monad is simply a triple (that's why it's called a monad, ... because it's a triple), defined thusly:

(T, η, μ)

Simple right?

Don't leave me!

Okay, yes. I understand you are rolling your eyes and saying 'well, that's all Greek to me.'

So allow me to explain in plain language the monad.

Monad is the triple (T, η, μ) where

T is the Monad Functor
η is the unit function that lifts an ordinary object (a unit) into the Monad functor; and,
μ is the join function that takes a composed monad M (M a) and returns the simplified type of the composition, or M a.

And that is (simply) what the hell a Monad is. What a monad can do ... well, there are articles galore about that, and, later, I will provide examples of what Monad gives us ... in Java, no less.

The Implementation

We need to work our way up to Monad. There's a whole framework, a way of thinking, a context, that needs to be in place for Monad to be effective or even to exist. Monad is 'happy' in the functional world, so we need to implement functions.

Or more correctly, 'functionals' ... in Haskell, they are called 'Functors.'

A functor is a container, and the function of functors is to take an ordinary function, which we write: f: a → b (pronounced "the function f from (type) a to (type) b" and means that f takes an argument of type a and returns a result of type b), and give a function g: Functor a → Functor b.

Functor basically is a container for the function fmap: Functor f ⇒ (a → b) → (f a → f b)

Well, is Functor the fundamental type? Well, yes and no.

It is, given that we have functions defined. In Java, we don't have that. We have methods, yes, but we don't have free-standing functions. Let's amend that issue:


  public interface Applicable<T1, T2> {
      public T2 apply(T1 arg) throws Failure;
  };

And what's this Failure thingie? It's simply a functional exception, so:


  public class Failure extends Exception {
      public Failure(String string) { 
          super(string); 
      }
  
      /// and the serialVersionUID for serialization; your IDE can define that
  }

I call a Function 'Applicable' because in functional languages that's what you do: apply a function on (type) a to get (type) b. And, using Java Generics terminology, type a is T1 and type b is T2. So we're using pure Java to write pure Java code and none will be the wiser that we're actually doing Category Theory via a Haskell implementation ... in Java, right?

Right.

So, now we have functions (Applicable), we can provide the declaration of the Functor type:


  public interface Functor<F, T> {
       public <T1> Applicable<? extends Functor<F, T>,
                              ? extends Functor<F, T1>>
          fmap(Applicable<T, T1> f) throws Failure;
  
      public T arg() throws Failure;
  }

The above definition of fmap is the same declaration (in Java) as its functional declaration: it takes a function f: a → b and gives a function g: Functor a → Functor b

Okay, we're half-way there. A Monad is a Functor, and we have Functor declared.

The unit function, η, comes for free in Java: it's called new.

So that leaves the join function μ.

And defining join for a specific monad is simple. Join for the list monad is append. Join for the Maybe monad and the ID monad is arg. What about join for just Monad?

Well, there is no definition of such, but we can declare its type:


  public interface Joinable<F, T> extends Functor<F, T> {
      public Functor<F, ?> join() throws Failure;
  }

Too easy! you complain.

Well, isn't it supposed to be? Join is simply a function that takes a functor and returns functor.

The trick is that we have to ensure that T is of type Functor<F, ?>, and we leave that an implementation detail for each specific monad implementing join.

That was easy!™

Monad

So now that we have all the above, Functor, Join, and Unit, we have Monad:

... BUT WAIT!

And here's the interlude of where the power of Monad comes in: bind.

What is bind? Bind is a function that says: do something in the monadic domain.

Really, that sounds boring, right? But it's a very powerful thing. Because once we are in the monadic domain, we can guarantee things that we cannot in Java category (if there is such).

(There is. I just declared it.)[2]

So, in the monadic domain, a function thus bound can be guaranteed to, e.g., be working with an instance and not a null.

Guaranteed.

AND! ...

Well, what is bind?

Bind is a function that takes an ordinary value and returns a result in the monadic domain:

Monad m ⇒ bind: a → m b

So the 'AND!' of this is that bind can be chained ... meaning we can go from guarantee to guarantee, threading a safe computation from start to finish.

Monad gives us bind.

And the beauty of Monad? bind comes for free, for once join is defined, bind can be defined in terms of join:

Monad m ⇒ bind (f: a → m b) (m a) = join ((fmap f) (m a))

Do you see what is happening here? We are using fmap to lift the function f one step higher into the monadic domain, so fmap f gives the function Monad m ⇒ g: m a → m (m b) so we are not actually passing in a value of type a, we are passing in the Monad m a, and then we get back a type of m (m b) which then join does it magic to simplify to the monadic type m b.

So to the outside world, it looks like we are passing in an a to get an m b but this definition allows monadic chaining, for a becomes m a and then m (m b) is simplified to m b that — and here's the kicker — is passed to the next monadically bound function.

You can chain this as far as you'd like:

m a >>= f >>= g >>= ... >>= h → m z

And since the computation occurs in the monadic domain, you are guaranteed the promise of that domain.

There is the power of monadic programming.

Given that explanation, and remembering that bind can be defined in terms of join, let's define Monad:


  public abstract class Monad<M, A> implements Joinable<M, A> {
      public <T> Monad<M, T> bind(Applicable<A, Monad<M, T>> f) throws Failure {
          Applicable<Monad<M, A>, Monad<M, Monad<M, T>>> a
              = (Applicable<Monad<M, A> Monad<M, Monad<M, T>>>) fmap(f);
          Monad<M, Monad<M, T>> mmonad = a.apply(this);
          return (Monad<M, T>) mmonad.join();
      }
  
      public Monad<M, A> fail(String ex) throws Failure {
          throw new Failure(ex);
      }
  }

The bind implementation is exactly as previously discussed: bind is the application of the fmap of f with the joined result returned. So, we simply define join for subclasses, usually a trivial definition, and we have the power of bind automagically!

Now fail is an interesting beast in subclasses, because in the monadic domain, failure is not always a bad thing, or even an exceptional one, and can be quite, and very, useful. Some examples, fail represents 'zero' in the monadic domain, so 'failure' for list is the empty list, and 'failure' for Maybe is Nothing. So, when failure occurs, the computation can continue gracefully and not always automatically abort from the computation, which happens with the try/catch paradigm.

There you have it: Monads in Java!

The rest of the story: ... Maybe

So, we could've ended this article right now, and you have everything you need to do monadic programming in Java. But so what? A programming paradigm isn't useful if there are no practical applications. So let's give you one: Maybe.

Maybe is a binary type, it is either Nothing or Just x where x is whatever value that is what we're really looking for (as opposed to the usual case in Java: null).

So, let's define the Maybe type in Java.

First is the protocol that extends the Monad:


  public abstract class Maybe<A> extends Monad<Maybe, A> {

Do you see how the Maybe type declares itself as a Monad in its own definition? I just love that.

Anyway.

As mentioned before, fail for Maybe is Nothing:


      public Maybe<A> fail(String ex) throws Failure {
          return (Maybe<A>) NOTHING;
      }

(NOTHING is a constant in Maybe to be defined later. Before we define it ('it' being NOTHING), recall that a Monad is a Functor so we have to define fmap. Let's do that now)


      protected abstract <T> Maybe<T> 
              mbBind(Applicable<A, Monad<Maybe, T>> arg) throws Failure;
  
      public <T> Applicable<Maybe<A>, Maybe<T>>
                  fmap(final Applicable<A, T> f) throws Failure {
          return new Applicable<Maybe<A>, Maybe<T>>() {
              public Maybe<T> apply(Maybe<A> arg) throws Failure {
                  Applicable<A, Monad<Maybe, T>> liFted =
                          new Applicable<A, Monad<Maybe, T>>() {
                      public Maybe<T> apply(A arg) throws Failure {
                          return Maybe.pure(f.apply(arg));
                      }
                  };
                  return (Maybe<T>)arg.mbBind(liFted);
              }
          };
      }

No surprises here. fmap lifts the function f: a → b to Maybe m ⇒ g: m a → m b where in this case the Functor is a Monad, and this case, that Monad is Maybe.[3]

There is the small issue(s) of what the static method pure and the method mbBind are, but these depend on the definitions of the subclasses NOTHING and Just, so let's define them now.


      public static final Maybe<?> NOTHING = new Maybe() {
          public String toString() {
              return "Nothing";
          }
          public Object arg() throws Failure {
              throw new Failure("Cannot extract a value from Nothing.");
          }
          public Functor join() throws Failure {
              return this;
          }
          protected Maybe mbBind(Applicable f) {
              return this;
          }
      };

Trivial definition, as the Null Object pattern is trivial. But do note that the bind operation does not perform the f computation, but skips it, returning Nothing, and forwarding the computation. This is expected behavior, for:

Nothing >>= f → Nothing

The definition of the internal class Just is nearly as simple:


      public final static class Just<J> extends Maybe<J> {
          public Just(J obj) {
              _unit = obj;
          }
  
          public Maybe<?> join() throws Failure {
              try {
                  return (Maybe<?>)_unit;
              } catch(ClassCastException ex) {
                  throw new Failure("Joining on a flat structure!");
              }
          }
          public String toString() {
              return "Just " + _unit;
          }
          public Object arg() throws Failure {
              return _unit;
          }
          protected <T> Maybe<T> 
                  mbBind(Applicable<J, Monad<Maybe, T>> f) throws Failure {
              return (Maybe<T>)f.apply(_unit);
          }
          private final J _unit;
      }

As you can see, the slight variation to NOTHING for Just is that join returns the _unit value if it's the Maybe type (and throws a Failure if it isn't), and mbBind applies the monadic function f to the Just value.

And with the definition of Just we get the static method pure:


      public static <T> Maybe<T> pure(T x) {
          return new Just<T>(x);
      }

And then we close out the Maybe implementation with:

}

Simple.

Practical Example

Maybe is useful for any semideterministic programming, that is: where something may be true, or it may not be. But the question I keep getting, from Java coders, is this: "I have these chains of getter methods in my web interface to my data objects to set a result, but I often have nulls in some values gotten along the chain. How do I set the value from what I've gotten, or do nothing if there's a null along the way."

"Fine, no problems ..." I begin, but then they interrupt me.

"No, I'm not done yet! I have like tons of these chained statements, and I don't want to abort on the first one that throws a NullPointerException, I just want to pass through the statement with the null gracefully and continue onto the next assignment. Can your weirdo stuff do that?"

Weirdo stuff? Excusez moi?

I don't feel it's apropos that functionally pure languages have no (mutable) assignment, as that throws provability out the window and is therefore the root of all evil.

No matter how sorely tempted I am.

So, instead I say: "Yeah, that's a bigger problem [soto voce: so you should switch to Haskell!], but the same solution applies."[4]

So, let's go over the problem and a set of solutions.

The problem is something like:


  try {
      foo.setD(getA().getB().getC().getD());
      foo.setE(getA().getB().getC().getE());
  
      bar.setJ(getF().getG().getH().getJ());
      bar.setM(getF().getG().getK().getM());
  

      // and ... oh, more than 2000 more assignments ... 'hypothetically'
  

  } catch(Exception ex) {
      ex.printStackTrace();
  }

And the problem is this: anywhere in any chain of gets, if something goes wrong, the entire computation is stopped from that point, even if there are, oh, let's say, 1000 more valid assignments.

A big, and real, problem. Or 'challenge,' if you prefer.

Now this whole problem would go away if the Null Object pattern was used everywhere. But how to enforce that? In the Java category, you cannot. Even if you make the generic Null Object the base object, the null is still Java's ⊥ — it's 'bottom' — as low as you go in a hierarchy, null is still an allowable argument everywhere.

And if getA(), or getB(), or getC() return null you've just failed out of your entire computation with an access attempt to a null pointer.

Solutions

Solution 1: test until you puke

The first solution is to test for null at every turn. And you know what that looks like, but here you go. Because why? Because if you think it or code it, you've got to look at it, or I've got to look at it, so here it is:


  A a = getA();
  if(a != null) {
      B b = a.getB();
      if(b != null) {
          C c = b.getC();
          if(c != null) {
              foo.setD(c.getD());
          }
      }
  }

What's the problem with this code?

Oh, no problems, just repeat that deep nesting for every single assignment? So you have [oh, let's say 'hypothetically'] 2000 of these deeply nested conditional blocks?

And, besides the fact that it entirely clutters the simple assignment:

foo.setD(getA().getB().getC().getD());

in decision logic and algorithms that are totally unnecessary and entirely too much clutter.

All I'm doing is assigning a D to a foo! So why do I have to juggle all this conditional code in my head to reach that eventual assignment.

Solution 1 is bunk.

Solution 2: narrow the catch

So, solution 1 is untenable. But we need to assign where we can and skip where we can't. So how about this?


  try {
      foo.setD(getA().getB().getC().getD());
  } catch(Exception ex) {
      // Intentionally empty; silently don't assign if we cannot;
  }
  
  try {
      foo.setE(getA().getB().getC().getE());
  } catch(Exception ex) {
      // ditto
  }
  

  try {
      bar.setJ(getF().getG().getH().getJ());
  } catch(Exception ex) {
      // ditto
  }
  

  try {
      bar.setM(getF().getG().getK().getM());
  } catch(Exception ex) {
      // ditto
  }

And I say to this solution, meh! Granted, it's much better than solution 1, but, again, you made a computational flow described declaratively in the problem to be these set of staccato statements, having the reader of your code switch into and out of context for every statement.

Wouldn't it be nice to have all the statements together in one block, because, computationally, that's what is happening: a set of data is collected from one place and moved to another, and that is what we wish to describe by keep these assignment grouped in one block.

Solution 3: Maybe Monad

And that's what we can do with monads. It's going to look a bit different that how you're used to the usual Java fair, as we have to lift the statements in the Java category into expressions in the monadic one.

So here goes.

First of all, we need to define generic functions (not methods![5]) for getting values from objects and setting values into object in the monadic domain:


  public abstract class SetterM<Receiver, Datum>
          implements Applicable<Datum, Monad<Maybe, Receiver>> {
      protected SetterM(Receiver r) {
          this.receiver = r;
      }
  
      // a monadic set function
      public final Monad<Maybe, Receiver> apply(Datum d) throws Failure {
          set(receiver, d);
          return Maybe.pure(receiver);
      }
  

      // subclasses implement with the particular set method being called
      protected abstract void set(Receiver r, Datum d);
  

      private final Receiver receiver;
  }

This declares a generic setter, so to define setD on the foo instance, we would do the following:


      SetterM<Foo, D> setterDinFoo = new SetterM<Foo, D>(foo) {
          protected void set(Foo f, D d) {
              f.setD(d);
          }
      };

The getter functional is similarly defined, with the returned value lifted into (or 'wrapped in,' if you prefer) the Maybe type:


  public abstract class GetterM<Container, Returned>
          implements Applicable<Container, Monad<Maybe, Returned>> {
  
      public Monad<Maybe, Returned> apply(Container c) throws Failure {
          Maybe<Returned> ans = (Maybe<Returned>)Maybe.NOTHING;
          Returned result = get(c); 
  

          // c inside the monad is guaranteed to be an instance
          // but result has NO guarantees!
  

          if(result != null) {
              ans = Maybe.pure(result);  
              // and now ans is inside the monad it must have a value.
              // ... even if that value is NOTHING
          }
          return ans;
      }
  

      protected abstract Returned get(Container c);
  }

With the above declaration, a getter monadic function (again, not method) is simply defined:


      GetterM<A, B> getterBfromA = new GetterM<A, B>() {
          protected B get(A a) {
              return a.getB();
          }
      };

In Haskell, the bind operator has a data-flow look to it: (>>=), so writing one of the 'assignments' is as simple as flowing the data to the setter:

getA >>= getB >>= getC >>= getD >>= setD foo

But we have no operator definitions, so we must soldier on using the Java syntax:


      try {
          getterA.apply(this).bind(getterBfromA).bind(getterCfromB).bind(getterDfromC).bind(setterDinFoo);
      } catch {
          // a superfluous catch block
      }

That's one of the assignment expressions.[6]

Let's walk through what happens with a couple of examples.

Let's say that A has a value of a, but B is null. What happens?

getterA forwards Just a to getterBfromA
getterBfromA gets a null, converts that into a NOTHING and forwards that to getterCfromB
getterCfromB forwards the NOTHING to getterDfromC
getterDfromC forwards the NOTHING to setterDinFoo
setterDinFoo simply returns NOTHING.

And we're done (that is: we're done doing, literally: NOTHING).

Let's counter with an example where every value has an instance:

getterA forwards Just a to getterBfromA
getterBfromA gets a b, converts that into Just b and forwards that to getterCfromB
getterCfromB gets a c, converts that into Just c and forwards that to getterDfromC
getterDfromC gets a d, converts that into Just d and forwards that to setterDinFoo
setterDinFoo gets the wrapped d and sets that value in the Foo instance.

Voilà!

The beauty of this methodology is that we can put them all into one block, and every expression will be evaluated and in a type-safe manner, too, as NOTHING will protect us from a null pointer access:


      try {
          getterA.apply(this).bind(getterBfromA).bind(getterCfromB).bind(getterDfromC).bind(setterDinFoo);
  System.out.println("Hey, I've executed the first assignment");
  getterA.apply(this).bind(getterBfromA).bind(getterCfromB).bind(getterEfromC).bind(setterEinFoo);
  System.out.println("...and the second...");
  getterF.apply(this).bind(getterGfromF).bind(getterHfromG).bind(getterJfromH).bind(setterJinBar);
  System.out.println("...and third...");
  getterF.apply(this).bind(getterGfromF).bind(getterKfromG).bind(getterMfromK).bind(setterMinBar);
  System.out.println("...and fourth...");
  
  // another more than 2000 of these expressions
  System.out.println("...and we're done with every assignment we could assign...");
  

      } catch {
          // a superfluous catch block
      }

And, because the monadic Maybe works it does, every assignment that can occur will, and ones that cannot will be 'skipped' (by flowing NOTHING through the rest of the computation, and the proof will be in the pudding ... on the standard output will be all the statements printed.

Summary

We presented an implementation of monads in Java, with a concrete example of the Monad type: the Maybe type. We then showed that by putting a computational set into the monadic domain, the work can be performed in a type-safe manner, even with the possible presence of nulls. This is just one example of practical application of monadic programming in Java: the framework presented here confers the benefits of research of monadic programming in general to projects done in Java. Use the framework to discover for yourself the leverage monadic programming gives.

End notes


[1]	Exact verbage:Phil says:January 14, 2009 at 7:01 pmI think that this could all be easily cleared up if one of you FP guys would just show us how to write one of these monad thingies in JavaâTo which a semi-mocking response was: 'you know, objects would be a lot easier for me to understand if you provided an implementation in Haskell.'Exact verbage:Cory says:April 23, 2009 at 6:26 amI may be a bit late to the game here, but Phil, that can be rephrased:I think that this could all be easily cleared up if one of you OO guys would just show us how to write one of these object thingies in HaskellâOf course you can, but it's a different type of abstraction for a different way of thinking about programmingâI write 'semi-mocking,' because: 1. OOP with message passing has been implemented in a Haskell-like language: Common Lisp. The Art of the Metaobject Protocol, a wonderful book, covers the 'traditional' object-oriented programming methodology, and its implementation, quite thoroughly and simply.
[2]	I leave it as an exercise to the reader to scope the Java category (Consult the Ω-calculus papers, Cardelli, et al;).
[3]	`Monad`<`Maybe`, `A`> and `Maybe`<`A`> are type-equivalent (but try telling the poor Java 1.6 compiler that).
[4]	"The same solution applies!" Geddit? Haskell is an applicative language, so the same solution applies! GEDDIT?
[5]	The distinction I raise here between methods and functions is the following: a method is enclosed in and owned by the defining class. A function, on the other hand, is a free-standing object and not necessarily contained in nor attached to an object.
[6]	Again, there is a distinction between an expression and a statement. An expression returns a value; a statement does not. A statement is purely imperative ... 'do something.' On the other hand, an expression can be purely functional ... 'do'ing nothing, as it were, e.g.: `3 + 4`. A pure expression has provable properties that can be attached to it, whereas it is extremely difficult to make assertions about statements in the general sense. The upshot is that having pure (non-side-effecting) expressions in code allows us to reason about that code from a firm theoretical foundational basis. Such code is easier to test and to maintain. Side-effecting statement code make reasoning, testing and maintaining such code rather difficult.

Attributed Variables: their uses and one implementation

2011-04-14T12:47:00.000-07:00

Here's a problem that comes up enough, computationally: find a value within some range. You don't know what the value is at the moment, but you will know it, eventually, as the range becomes further restricted by refinements of the constraints or data.

Now, in general, this is an easy problem for Haskell to solve, and Haskell provides more than one way to approach the solution. For example, if we have some x in some domain D, one way to look at an arbitrary x until we find the one, true x we are looking for is the following code snippet:

> [ x | x <- D, ... further constraints ]

More variables? Interrelated ones? No problem:

> [ (x, y, z) | x <- D, y <- D, z <- D, x < y, ... further constraints ]

Okay, let’s take it to the next level. What if the interrelation is such that one variable consumes from the domain, so that value is now unavailable to other variables. Pithily: the variables’ values are mutually exclusive.

Well, one way to go about that is to embed a guard for each variable into the list compression:

> [ (x, y, z) | x <- D, y <- D, y /= x, z <- D, z `notElem` [x,y], ...

The drawback here is that this kind of guarded coding becomes tedious and prone to errors. On top of that we see that the guard follows the select, causing unnecessary backtracking through the search space,[1] especially given that we know the guarded values a priori.

Well, then, we can automate guarded selection with a state (transformer) monad:[2]

> ...
> f = do x <- choose
>        y <- choose
>        z <- choose
> ...
> runStateT f [0..9]

Okay, excellent! All of this works and works well … for a fixed and predetermined variable set.

The Problem

Things start to get tricky for me, programmatically, however, when one set of constrained values spill over onto another set of constrained values, such as the results of one generation in a cellular automata set or genetic (algorithm) pool affect the next set:

> evalStateT (gen row1guards) domain >>= \ans1 ->
>   evalStateT (gen (row2guards ans1)) domain >>= \ans2 ->
>     evalStateT (gen (row3guards ans1 ans2)) domain >>= \ans3 ->
> ... etc

The state transformer isn’t enough, so it needs to be some RWS monad, perhaps pushing the interim results into the Reader monad and the accumulated ones into Writer while the State monad handles the flow of the computation?

It seems to me that the work becomes more about monad management and less about the computation itself.[3]

Then there’s the even more general computation. What if we do not know, a priori, how many values we are generating in our problem solving? The problem space I’m looking at is something like:

For a variable number of variables, map selection and guards for each variable.

How do I write that as a list compression expression, or as a monadic one? The problem with Haskell variables is that they aren't (variables), and so something so easily accomplished in a Prolog program:

kakuro([], Vars, Functor) :-
    Fn =.. [Functor, Vars],
    call(Fn).
kakuro([H|T], Acc, Functor) :-
    assign(H),
    kakuro(T, [H|Acc], Functor).

called with:

?- kakuro([A, B, C, D], [], sum_equals_10).

or:

?- kakuro([X, Y, Z], [], sum_equals_10).

... or with a list of any other length isn't so easily written out in Haskell when I go to attack the problem. After all, what is the type of a list of unbound variables? Haskell doesn't (so easily) allow this, and I was stuck: I didn't know how to proceed using monadic programming or list compression.

A solution

Fortunately for me, I've been studying constraint-based programming, and that research has let me to some papers on attributed variables[4] which faciliate that programming style.

Attributed variables are variables ranging over a domain that can have attributes attached to them that restrict (or constrict) the range of values. It's a very simple step to go from a set of unbound attributed variables to a (simple or façile) constraint solver by adding (constraining) attributes to the variables.

More formally, I declare (denotationally) an attributed variable as:

> data Attribute a = Attribute [Constraint a] (Domain a)

where Constraint and Domain are declared as:

> newtype Constraint a = Constraint { resolve :: a -> Bool }

> type Domain a = [a]

Or, to put words to it, an Attributed Variable is an object that has a set of (constraining) functions over an assigned domain.[5]

The above denotational declaration of attributed variables works, but I find, operationally, grounding an attributed variable once it's reduced to a single value to be useful:

> data Attribute a = Attribute [Constraint a] (Domain a)
>     | Ground a

So, that's my declaration.[8] How is this implemented in practice?

Implementation

The approach I take is that an attributed variable is created in a free state over its domain:

> makeAttrib :: Domain a -> Attribute a
> makeAttrib list = Attribute [] list

And then, as constraints are added to the attributed variable, the system 'tries to solve' the attributed variable over the set of the constraints:

> constrain (Attribute constraints dataset) constraint
>    = solve (Attribute (Constraint constraint:constraints) dataset)
> constrain (Ground x) _ = Ground x

And if the solution results in a singleton list, then the attributed variable becomes Ground:

> solve attr@(Attribute _ []) = attr
> solve attr@(Attribute constraints list@(h:t))
>    = let result = solve' constraints list
>      in if length result == 1
>         then Ground (head result)
>         else Attribute constraints result

Of course, the 'solution' to a Ground attributed variable is itself:

> solve (Ground x) = Ground x

The above code is simply a dispatch along the binary type. The worker-bee, solve' is simply (again) an implementation of the dual of filter:

> solve' :: [Constraint a] -> [a] -> [a]
> solve' _ [] = []
> solve' constraints (h:t) =
>    if   (solveConstraints constraints h)
>    then (h:solve' constraints t)
>    else solve' constraints t

> solveConstraints :: [Constraint a] -> a -> Bool
> solveConstraints [] _ = True
> solveConstraints (f:rest) x = resolve f x && solveConstraints rest x

So something from Control.Applicative to reduce that to a one-liner? I leave that as an exercise to the reader.

And there you have it, that is a working implementation of attributed variables. I have test functions for groundedness, solvability and the current state of the domain of an active attributed variable, but those are simple helper functions, easily implemented, and provided in the attached source code.

Uses

So, now, what do we have?

Now we have variables over which we may specify a domain ('loosely' typing a variable) and then constrain. How can we use such a system?

One way is that we can write constraint logic programs in Haskell. The illustration from Prolog (above) has a nearly direct transliteration into Haskell (with the additional benefit of strong typing):

> kakuro :: [Int] -> Int -> [[Int]]
> kakuro list total = nub $ summer (sort $ map trib list) [] total

> trib :: Int -> Attribute Int
> trib x | x == 0    = makeAttrib [1..9]
>        | otherwise = Ground x

> summer :: [Attribute Int] -> [Int] -> Int -> [[Int]]
> summer [] list total = do
>    guard $ sum list == total
>    return $ sort list
> summer (h:t) list total = do
>     a <- domain $ constrain h (flip notElem list)
>     summer t (a:list) total

And with the above code, we can now do the following:

*Kakuro> kakuro [0,0,0] 10
[[1,2,7],[1,3,6],[1,4,5],[2,3,5]]
*Kakuro> kakuro [0,0,0,0] 10
[[1,2,3,4]]

Note that I use sort above, but attributed variables are not (denotationally) ordered types. Operationally, that is: in logical programming, it makes sense to eliminate early, so if we have Ground values, we wish to consume those first. So, to that end, I declare the following instances:

> instance (Eq a) => Eq (Attribute a) where
>     Ground x == Ground y = x == y
>     _        == _        = False

> instance (Ord a) => Ord (Attribute a) where
>     Ground x <= Ground y = x <= y
>     Ground _ <= _        = True
>     _        <= _    = False

And with those instance declarations, sort automagically works. Neat!

Interlude: Haskell is "Neat"

I don't know about you, but I'm guessing that many of you are taking the gift that Haskell is for granted. Or I suppose I should say 'the way of thinking that using Haskell provides.' Over and over again in industry (yes: stone knives and bearskins) I hear 'that can't be done.' And I find myself puzzled. What's the showstopper here?

For example, this past week at work, we needed to convert a data mapping document in Excel (stop snickering, please) into an equivalently flat XML schema representation with a accompanying XML sample file. So fields of the form:

/Field/Name="BusinessAddress"
/Field/Value="plaintext"

/Field/Name="BusinessAddress"
/Field/Value="encrypted"

And there were enumerated values as well:

/Field/Name="PropertyOccupancyTypeOwnerOccupied"
/Field/Value="plaintext"

/Field/Name="PropertyOccupancyTypeRentedToTenant"
/Field/Value="plaintext"

/Field/Name="PropertyOccupancyTypeVacant"
/Field/Value="plaintext"

There were over 1,000 of these element names. I mentioned I would write a parser to generate the XSD and XML and was told by the development team point-blank that that was impossible and the only way to go about this transcription was manually, line-by-line, by hand.

So I wrote the script. I suppose I could have used Perl, but as I'm on a Windows box, the shell isn't very inviting for Perl-like piping, so I used Haskell, stripping the metainformation and pushing the parsed names into a map (or, to be precise, a Data.Map) where enumerated (mutally exclusive instance) types went into a list named by their type name and other values were singletons. Then for the XSD I simply iterated over the elements of the map (recursively), and for the sample XML file, I just chose an element (in this case, the first element) of each type.

The net result was that all the elements analysis team compiled into an Excel spreadsheet by hand over a six week period I was able to deliver in two days as a full XSD schema and a comprehensive XML sample file.

Two members from the development team assisted me on this task, one of them was the lead developer. He was intrigued and asked me: "What does this script do?" after being impressed that he could generate a schema definition file and a sample file in seconds. So I explained Haskell as a 'data-flow' language and I traced the flow of the input file through the monad and function composition showing the translation of the internal representation into XSD and then, in a different context, into XML. I'm not sure he got my explanation, but he did walk away impressed with what Haskell can do.

Yes, these are simple things: parsing, mapping, iterating. But for most of the software engineering community in industry, it is easier and faster to go through, line-by-line, by hand, than to write a piece of code to automate that process ("Can that even be done?" "No, it's impossible, just do it manually").

I have encountered this over and over again in industry. Teams are willing to expend more than two hundred person hours to a reoccuring task and are willing to accept the associated fatigue errors to schedule systems by hand. Then they are shocked that I build a functional or logic-based system that autogenerates a pristine result in sub-second time.

Where does this leave us?

What I see as status quo is that industry is resigned to slog through repetitive tasks manually, because it's too hard in Language X to consider tackling the problem: more time would be spent writing, compiling and fixing a program to do the task than to do the task by hand.

On the academic side, I see researchers isolated from industry, feeling their advances have no practical use as there appears to be no interest from industry. I attended a talk on dependent types where the thesis was that this typing makes coding more declarative, more powerful and less error prone. I approached the lecturer and asked how I could implement such a system and was asked what application dependent types had for industry.

Hm. Let me think on that for a while.

Why would industry be interested in coding more declaratively, more powerfully, and with less errors? I was flabbergasted that the researcher saw no benefit for industry in his presentation.

We have a powerful tool in Haskell. We can do more, cleaner, safer, and do it faster than the mainstream alternatives industry picks over and over again by default.

I've found, however, that talking about typing, or monads, or pure functional programming only causes the eyes to glaze.

What lights a fire in management's eyes? When you rescue an overdue project, delivering before the deadline, and you educate other workers to be as productive ... perhaps not writing Haskell themselves (I've been asked: "Is it like Pascal?" ... and that's after a code walkthrough), but using the tools you've used to deliver these 'tremendous' results, and earning their trust that when you say, 'just let me write a Haskell script to do that: I'll take a day to write it, and we'll start getting results right away,' that that is actually what happens. I've found that 'we should use Haskell because of [all the wonderful arguments put forward]' does not convince anybody. Delivering 'incredible' and 'impossible' results, significantly faster than anticipated (two days instead of two months for the XML project)? That moves mountains.

Where I work, Haskell is installed on two lead developer's systems other than my own, and I'm given permission to code in Haskell, on a 'we only allow Language X' project.

Other Uses

So attributed variables can be used to help one solve kakuro puzzles, or to write a sudoku solver. Fine.

And I've been inching my way toward attributed variables, so it can be applied to symbolic logic puzzles as well, replacing my Whatever type with attributed variables over the enumerated domain.

So the domain is not restricted to Number, but these are not very interesting or pragmatic examples in and of themselves. Not very gripping.

So how about this example?

*Stocks> makeAttribute [Buy, Sell, Hold]

with Constraints being input feeds filtered through weighted moving averages and other indicators. Now this is a system of keen interest for me and 'currently under active and intense research.'

Will such a system work or not work? I'm not at liberty to say,[9] but here is an area that appears to fit well in the language space of constraint programming.

As problem spaces attacked by software projects — workflow analysis, data mining, planning and scheduling, budgeting, forecasting, (war)gaming, modelling and simulation — many seem good candidates to use constraint-based reasoning. Attributed variables give Haskell programmers another way to express these problem domains.

Endnotes:

[1] Y’all don’t mind if I speak logically, and in the logic-programming paradigm, do you?

[2] See my article in The Monad.Reader, issue 11, “MonadPlus: What a Super Monad!” for an implementation of choose, et al.

[3] No, I’m not speaking disparagingly of the monadic programming style. I rather like that style, and use it in my domain language of predicate logic that I layer on top of ‘regular’ Haskell programming. The beauty of monads, for me, is that they are invisible (in coding them) and powerful (in their effect). When the code becomes more about monads and less of what they are there to do is when I see this as an opportunity to examine things in a different light.

[4] http://www.swi-prolog.org/pldoc/doc_for?object=section(2,'6.1',swi('/doc/Manual/attvar.html'))

[5] My representation of Domain is straightforward and workable for most cases, but it hides more than a few compromises (or 'sell-outs') beneath the surface. For example, it makes the (gross) assumption that the range of the domain is enumerable. If Domain is in ℜ that no longer holds (at all), so then Domain shouldn't have a list representation but a pair (or bookending) bounds. But then what if Domain extends beyond ℜ and goes into the surreal numbers?[6] Then we have infintesimals such as '*' (pron: 'star') where:

* > 0, * < 0, * + * = 0

and:

* || 0 (that is: 'star' is incomparable to 0)

So how does one bounds-check on incomparables?

But these concerns are, in the main, not ones to lose one's head over. For the most part, simple linear programming solves a vast majority of the World's problems,[7] and those interesting cases are exactly that: interesting cases.

[6] http://en.wikipedia.org/wiki/Surreal_number

[7] The preface of How to Solve It: Modern Heuristics by Zbigniew Michalewicz and David B. Fogel makes this assertion, from hard-won experience in the field. Seconded.

[8] This is one approach to attributed variables, that is: constraints or attributes are applied to the variable over the domain until it is reduced to a single value, at which point the constraints and even the domain become superfluous and simply go away. An advantage to this approach is that a test for groundedness becomes trivial. A disadvantage is that once grounded one loses the path or information that got one there except through the data flow through the algorithm (the stack trace, as it were). Another disadvantage is that an attributed variable, once grounded, automatically rejects constraints. This may lead to unexpected program behavior, because AV grounded to 5 with a new constraint of x > 23 should fail, but my implementation forwards the 5 value in a success state.

[9] An audit trail of at least a year of data is necessary before any claims can be made.

'List' leads off with the letter 'Lambda' (λ)

2010-09-14T08:35:00.000-07:00

I was revisiting the Project Euler problems recently, and one of the problems addressed lexicographic permutations.

Well, problem solved if you're using C++ or other languages that have lexicographic_permutation packaged with their standard library set. Some languages do and some don't, but that discussion is not à propos to this article, nor even what lexicographic permutations are or how to go about getting to them.¹

But something common enough did come up in the solving of that problem, which is the question of appending to the end of lists effectively.

Now, I have a prejudice: I love lists, and by that I mean to say is that in more than a few functional and logical programming languages, the List Data Structure (uttered with reverence, and with not even (barely) a hint of mocking) provides a facility for grouping and then operating on sets of objects that I find unparalleled in other programming languages and paradigms. I can, for example, in Haskell create a list simply by typing [0..9] or ["Mary", "Sue", "Bob"], and if I'm feeling old-fashioned and gutsy, I can iterate through those lists inductively with a:

doSomething [] = []
doSomething (h:t) = f h : doSomething t

Or if I wish to embrace the modern era of programming (like, oh, since the 1970ish-es),² I can use map or fold to go anywhere I want to with a list. I mean, come on! fold is, after all, the 'program transformer function.' If I don't like my list as it is now (or if I don't even like it being a list at all), I just fold over it until it's exactly how I want it to be.

Like the above function, it's really just a specialization of map, isn't it?

map _ [] = []
map f (h:t) = f h : map f t

And map is just a specialization of fold, right?

foldr ((:) . f) [] ≡ map f

So, yeah, lists rock my world.

But, you complain, I know language X [yes, the great language (flame-)war, with endless debates in the imperial senate, continues] and language X has lists and map, so what's the big deal?

The big deal is this: have you ever tried to construct a list in language X? Is it easy as the example I provided above?

No, but ...

Yeah, no, it's not as easy. In fact, I've done quite a bit of programming in language X, and I put forward that constructing and then destructuring lists is a painfully long and tedious process:

BidirectionalLinkedList list = new BidirectionalLinkedList();
list.add("Mary");
list.add("Sue");
list.add("Bob");

Blech!

BUT THEN it gets better when you do destructuring:

BidirectionalLinkedList newlist = new BidirectionalLinkedList();
for(String elem : list) { newlist.add(doit(elem)); }

Um, and that's only after the "stunning" advances that the STL started with functionals³ grafted onto the language, so have you seen the contortions you have to go through to create a functional object to map with? And don't you dare get your template parameter off because the compiler error...? shudder!

Enough of that.

So lists are structures or collections, and structures can be viewed as objects (phenomenon), and that is a very useful and powerful way to view them and to define them:

data List t = [] | (t : List t)

No problem with that and everything is right with the world.

... until it isn't.

This definitely works, and works well, for lists in general, and it also works great most of the time for working with the elements of the list. After all, in practice, we are most concerned with the element we have worked on most recently, so, in most cases, the element we just put in is the element we'd most likely to be retrieving ... AND (generally) our interest diminishes the further (in time) we are from an element, and that translates directly into where elements are found in a list.

Generally.

So, in general, lists work just fine; great, in fact.

There are specific cases where what we care about is not the most recent element, but another ordering is important. Two cases spring immediately to mind: first, queuing, and secondly (and commonly and specifically), document assembly.

In these two cases we wish to push onto the end of the list new elements, and the above definition doesn't give us access to the last element or position of the list. And to get that access, we must reverse the list so the last element becomes the first, or prepend to a reversed list. Either of these options has at least a cost in linear time when reverse is (eventually) called.

Or, we must call append or a function like it to append elements to the end of the working list; this also has linear costs. Either way, we pay the full price.

Now there are objects that do give us immediate access to that last element and position: deques and queues, for example, but when we go there, we give up the ease of composition and decomposition that we have with lists. We pay a penalty in expressitively with these types or in performance when using lists against their nature.

Or do we?

Well, one way of looking at lists is as objects, and above we gave a definition of lists as objects, but this is not the only way to view lists. I propose another way of looking at lists: lists can be viewed as functions.⁴

(:) :: t → [t] → [t]

The above definition says that (:) (pronounced 'cons') takes an element and a list and gives a list.

Yeah, so? you ask, for this is already a well-known function in the list lexicon.

I propose we look at this function in an entirely different way:

(:) :: t → ([t] → [t])

In this case, (:) constructs a list function from a seed element. This allows us to use this function a novel but perfectly acceptable way:

x |> list = (x:) . list

What we are saying here is that (|>) (pronounced 'put to front') is an operator that takes an x and puts that value on the front of list, just like (:) does.

The difference here (heh: 'difference') (sorry, mathematician humor) is what list is. For (:), list is of type [a] (or, directly and tautologically: list is a list), but for (|>), list is of type [a] → [a]. Or, translating: list is a function.

So? You've just reinvented the wheel with lists as functions now. Big deal.

Well, actually, what I've done is to reinvent the wheel as a meta-wheel, and so the big deal is this:

list <| x = list . (x:)

What we have here with (<|) (pronounced 'put to back') is a function that adds an element to the end of a list in — wait for it! — constant time. For 'regular' lists the best you can do that operation is in linear time, and so my work of constructing a document by appending to the end of a list that was occurring in O(n²) time has just gone to a linear-time operation. Not a big deal for a small document, but we found that once a document became more than a page or two, the operation went from 'a blink of an eye' to 'keeping your eyes closed until the cows came home ... that had been eaten by wolves.' This is not the case with lists as functions: document construction became reasonable endeavor (that is, it occurred so quickly for us mere humans, living in this non-nanosecond-time, we didn't notice the elapsed time).

So, I've been a sly thing in one respect. I still haven't told you what a (functional) list is. I've defined the object view of lists, and I've declared what a function view of lists, but haven't defined them.

Here. Allow me to define them now:

empty = id

There you go. There are the 'definitions.' I say 'definitions' because with that sole definition, everything works, for to ground a functional list, we simply pass it an empty list:

empty [] ⇒ []

Or even whatever list we are working with:

empty [1,2,3] ⇒ [1,2,3]

When you append something to an empty list, you get that something back.

AND empty works as the seed of the 'put to' operators:

(5 |> 6 |> 2 |> empty) [1,2,4] ⇒ [5,6,2,1,2,4]

and:

(empty <| 1 <| 2 <| 3) [4,5,6] ⇒ [1,2,3,4,5,6]

It all works!

Summary
In this article we've demonstrated that there's more than one way to look at, specifically, lists. The standard way is to view them is as objects, and for the most cases, that works, and works well: this view provides a syntax that makes list processing simple and intuitive.

We've also shown that that is not the sole way to view things, and this view can be constraining, particularly when lists are played against type as a queue or a document assembler. In these cases it becomes simpler, declaratively, to view lists as functions, and not only does that provide a syntax for simple list construction either at the beginning or the end of the list, but also provide constant-time construction at either end. Furthermore, defining this view is as simple as viewing the empty list as id and then using the partial function of (:) ('cons'). That's the generative view. Then, to extract the ("real") list from that view, it's as simple as sending a list (for example, []) to that functional list to ground the value for disposition.

In these special cases of working at the back end of a list, that aren't all that rare, the functional view of list processing gives the programmer expressivity and efficiency, eliminating the chore of appending to the end or reversing the target list. I quite enjoy list processing this way: it gives me a fresh perspective on an old friend and makes list processing in these cases easy and fun.

Endnotes

¹	There is an article at http://wordaligned.org/articles/next-permutation that provides a simple, clear explanation of the lexicographic permutation algorithm with a very nice demonstrative example if you are so inclined to investigate.
²	Laurent Siklóssy, Let's Talk Lisp talks about `MAPCAR` in chapter 6. And, if I may: this book is one of the rare ones. It's one of those books like Smullyan's To Mock a Mockingbird or van der Linden's Deep C Secrets (with a fish on the orange book cover, no less!) or, and let us not forget the ultimate: Hofstadter's Gödel, Escher and Bach: the Eternal Golden Braid (I mean, even the title is a pun, Doug doesn't waste time in having fun, does he? He gets right to it!) that make you a better person but you don't notice it, but everybody else does, because you are constantly busting out laughing or grinning from ear-to-ear at the cleverness of their prose. Why do books about esoterica have to be so heavy! These esoteric books show that they don't have to be heavy in the lightness they deal with the subject (and deal with dealing with these esoteric subjects). And who is that bright young man who left such a feisty review of that book back in (le gasp!) 2001? I can see a promising future for that boy, just so long as he doesn't get too big for his britches. À propose de rien, what are britches? ahem Yes, so those books are three of my favorites ... which ones are yours?
³	Bjarne Stroustrup, The C++ Programming Language, 3rd ed., §18.4
⁴	Such a view of lists has a name: these functional list types are called difference lists from the Prolog community. The standard Haskell library does not have `Data.DList` [sad loss, I say!] but this type is provided by Don Stewart of Galois in the hackageDB under the dlist package. The `Data.DList` works great, but I've implemented my own system that is more than twice as fast as I provide several specialized implementations of difference list operators that take a more direct approach in their implementations (`foldr` is elegant but can be a costly operation). If you'd like to use my `Data.DiffList` package please contact me, and I'll be delighted to share this library.

Math is hard

2010-05-26T07:24:00.000-07:00

So, here's an interesting, everyday conundrum, sent to me by a reader:

Hello my mathematical genius friend. :) [should I edit that out? *blush*]

I have been sent the following mathematical joke of sorts. The person who sent it to me claims there are no flaws in it. But obviously there has to be a flaw, because the conclusion is incorrect. The problem is that I don't know how to explain the flaw---but I suspect it happens in that third line where it attempts to equate squared cents with squared dollars. Is there any way that you could explain the flaw in such a way that a seventeen year old Norwegian would understand? Don't worry, you don't have to say it in Norwegian, he speaks English.

If you don't mind having a look at this and explaining, I would be ever so obliged. And no pressure, but...pants may be on the line in this little bet I've entered into.

1. $1= 100¢ (so $0.1 = 10¢)
2. And, 100¢ = 10¢²
3. Then, 10¢² = $0.1²
4. $0.1² = $0.01
5. $0.01 = 1¢

The implied conclusion is

∴ 'a dime squared equals one penny'

Then we say 'Q.E.D.'.

Hm, if pants are on the line for my dear reader, I wonder what's on the line for moi-self (that is faux-French) (and 'faux' is French)? A review? Or two? Or three? Of my stories?

Let's leave my preening aside.

So, who sees the fallacies above that lead to the absurd conclusion?

If you do not see it, please think on this awhile before looking at the answer.

The answer

From basically the get-go this problem statement is erroneous and imprecise, but this comes from a fundamental laxity in understanding of what operators are and what operators do. Certainly, the first premise is correct: One hundred pennies does indeed equate to one dollar, for

1. 100¢ = $1

is a statement of fact about the conversion from one set of units (pennies or ¢) to another set (dollars or $). But already the trickster plays fast and loose, for indeed:

1. ... (so $0.1 = 10¢)

is still correct but the (implied) conclusion makes a statement about the square of dimes, not about the square of tenths of dollars.

Do you see the fallacy now?

No? Let's continue.

So 1. is true, insofar as I can throw it, and days where my back gives out (ah! me poor bones!) that's not very far, but it's far enough for this problem statement, so long as it goes no farther than that.

But it does. *sigh*

So now let's get into the lies:

2. 100¢ = (10¢)² [parentheses implied and erroneous]

This is a lie. It's a lie, lie, lie, lie, lie, lie, lie!

Huh?

The lie is this: a square of a thing is not the thing itself, and even if you know nothing about mathematics, you can prove this to yourself. Socrates did it with an unlettered and untutored slave boy, and you are further along than what Socrates had to work with.

So let's prove 2. false with an analogue.

Take a foot rule (sorry, my readers who do not follow the British Imperial system, which, oddly enough, includes Brits these days, too) and a large piece of butcher paper. Draw a line on the butcher paper measuring one foot.

a. _ = 1 foot.

Now, 'square' that line, by drawing three more lines to make a foot square on the butcher paper.

b. ❏ = 1 foot square.

So, is

c? 1 foot = 1 foot square

Obviously not! for that would be to say:

c? _ = ❏

Or, put another way, 'one thing of one thing is equivalent to one thing of entirely a different thing'. One gulp of water does not equal one gulp of bleach. One I wish to have with my breakfast, the other, I do not, as my father very unfortunately discovered the hard way one not-so-fine morning.

"But, but, but ..." you stutter angrily, "but isn't '10² = 100' a statement of fact?"

Yes, indeed, it is, but please remember '10 ≠ 10 things' is also a statement of fact. Number (with a capital 'N') is a class of classes as, e.g., Introduction to Mathematical Philosophy so clearly and succinctly explains.

The link goes right to the book, all 228 pages of it. It's a quick read, so please (re)read it.

So to state:

2. 100¢ = (10¢)² [parentheses implied and erroneous]

is to state a falsehood.

How do we correct it? Well, by replacing the (implied) error with an explicit (corrected) ordering:

2. 100¢ = 10²¢

Do you see the correction? It the former case, we erroneously squared the units along with the number, in the latter case we do not square the units, we square the number solely.

Do I need to go any further? Or, do the fallacies fall out obviously in the rest of the assertions?

For completeness sake, I will review each step.

3. (10¢)² = ($0.1)² [parentheses implied and erroneous]

No. (10 pennies) squared does not equal (1 dime) squared.
But, a statement of fact of conversion is that (10 pennies) = (1 dime), but that's as far as it goes, and no farther.

If we square pennies we have a new unit of measure called, I don't know: (¢²), and (¢²) does not equal dimes. Not in this world.

4. ($0.1)² = $0.01 [parentheses implied and erroneous]

Again, no.
Again: $(0.1²) = $0.01, but again, that is as far as you can go with that statement.

5. $0.01 = 1¢

is just a reformulation of the first statement and is true, yes, but redundant.

Remember from Frege's predicate calculus:

q |- p [read: 'q implied by p' or 'if p then q']

[Shoot! why don't they have an 'implied by' HTML character?]
But if:

¬p [read: 'not p' or 'p is not true (or provable)']

Then you can say anything you like for q, or, more correctly, you cannot say anything at all about q, because q does not depend on ¬p, it depends on p.

So, as it were: 'If I had done the laundry, we wouldn't have had this argument' and 'I didn't do the laundry' means I don't have a leg to stand on about why we had this argument, honey.

(Oops, sorry, ... but it's not like I have had this experience at all ...)

And, to the point of this article: 'If a (10 one-hundredths of a dollar) squared were to equal (10 pennies) squared, then ...'

Well, then anything, because '(10 one-hundredths of a dollar) squared = (10 pennies) squared' is false. So say away, because anything coming from a false premise is an absurd conclusion: whirled (black eyed) peas, butterflies flapping in the Amazon, and the Number 23. They may be true enough in their own right, but you can say nothing about them from the false premise.

So, let's take the absurd conclusion:

∴ 'a dime squared equals one penny'

and reformulate it to be a true statement.

Well, the first thing we have to do it to get rid of the '∴', so let's do that, and then state the plain facts:

'a dime squared equals one penny' is an absurdity.

Q.E.D.

What can we take away from this?

Let's examine another absurity:

'Math is hard.'

No.

No, my dear ladies and gentlemen, 'Math' isn't 'hard.' Math is simple. Math can even be easy, for we learned from the Greeks, after all, that Math is one of the humanities. Math is simply a language. A language that can describe things exactly as they are and exactly as they are not. And precisely at that. It can even describe imprecision precisely. The 'hard'ness of mathematics comes from us, when we don't wish to be precise in what we are talking or thinking about.

Being precise ... well, that can be hard, I suppose, so then perhaps it's more precise not to say 'Math is hard' but to say 'Life is hard.'

Yes. That's true. 'Life is hard' as we choose to make it.

Oh, well. I never promised you a Rose Garden.

Realized Constants are Comonadic

2009-06-02T11:13:00.000-07:00

An interesting problem that often arises is "to make" constants. Put another way, it often happens that a system acquires information over time. The system may wish to formalize what it has acquired by creating a constant value.

Here's the problem, however: "Variables don't; Constants aren't"^citation?

Or, put another way:

1. One man's constant is another man's variable.

To make a constant sometime down the road, as it were, in languages that have logic variables is simplicity itself: once a variable is unified with a value, it keeps that value throughout that proof.

In "pure" functional languages, that is, languages that do not have side effects, the same can be said.

What about the rest of the world? Take Java, for example. One can make a variable keep its value by declaring that variable final, but that is not helpful if we do not know what our constant value is to be at the time of object creation.

In what scenario could this possibly occur? We need a constant value, but we do not know what it is?

Actually, this situation arises quite frequently. Let's take a concrete example. You have many databases in your database management system, and at compile time you do not know on which port your DBMS is running nor do you know which database the user wishes to query. That's fine, you can lazily create the database connection and access the value through a method:

2. Functions delay binding; data structures induce binding. Moral: Structure data late in the programming process.

But what's not fine is this: the user is data-mining, examining chunks at a time, occasionally calling for the next chunk. How does one know that one has fallen off the end of the table? A simple SELECT on the maximum indexed key will tell you that, but to do that with every query? This seems wasteful. So, once we do the query once, let's just store that value in a variable with a flag to say we've already looked it up.

That sounds suspiciously like a lazily initialized constant, right?

But here's the rub: code that sets a flag allows for other code to unset it, just as code that sets a constant value allows other code to unset that. Using just plain-old regular variables gives no guarantee that the variable, once set, stays set at that constant value.

What to do?

Well, what is the work-flow of this process? We perform an action, checking that we are still within the bounds the valid domain, but the domain only becomes valid after program start, so we cannot make the bounds constant using the final keyword on the variable. This is a very common programming action ... sort of like ... dare I say ... a design pattern. Gee, I wish there was one invented that did all this.

In fact, there does exist such a pattern, and it comes from us via Category Theory. The programming language Haskell has incorporated elements of Category theory in its use of monads and arrows, but the downside of these ways of thinking about computation is that one must "lift" the entire computation into that domain, transforming the original computation to work in that regime.

No, what is needed is something less intrusive, and I found that less intrusive thing when I read an article by sigfpe on comonadic plumbing. In this article he describes three different ways of looking at constants: 1. as a constant, 2. as the Reader Monad, 3. or as the Reader Comonad.

The first one is sometimes untenable, given the programming need, and doesn't work for our case.

The second one is useful if one is already programming in a monad. Umm ... how many OO programmers use monads? Hands up.

[sound of crickets] ... thought so.

The third one allows one to use the constant on demand. And here's the thing, the comonad is very easily comprehended: it has a value that can be extracted "down" from the comonad, it allows a value to be extended over the comonad.

This sounds, in OO parlance, very much like an object. Let's ignore the extentionability of the comonad for now and simply look at extraction (this narrowed functionality is a thing in and of itself. Objects of this type are called Copointed, but let us not be too dogmatic here). Creating such a type is simplicity itself:

> public interface Comonad<T> { public T extract(); }

Um, yawn?

But that is the power of pattern language: not the ability to create these incredibly complex things in a controlled way (they do do that), but the ability to recognize that such and so is a pattern and then encapsulate behavior into the pattern.

Using the comonad pattern, we need simply to make our "maximum row number of Table x" an implementation of the Comonad interface, and then, when we do have enough information to create the database connection (that is, we now have our domain in which our constant resides), we instantiate the comonadic object (which is that domain). Whenever extract is called, it simply returns the constant value required, with the implementation that it does a database look up the first time, then it does the internal constant value look up all other times. Since the Comonad interface does not have methods to change its internals (here), so long as one has the copointed object, the value extract has a guarantee that it remains constant.

Summary

This article examined a commonly recurring problem: one needs to constify a value at some point during a program run and guarantee that it remain constant after being created. A simplification of the comonad was offered as a pattern that is simple to define and to implement.

Animal as RDR, part III

2008-09-29T18:21:00.000-07:00

Examples: Building, running and modifying RDR systems

The previous entries showed the implementation of the model of a simple Ripple-Down Rules (RDR) system. This entry will show how to implement the rules for such a system from scratch as well as how to run and then to modify such a system. Again, we are using the computer game Animal as the basis of these examples.

Let's start off by implementing RDR system modelled in the first entry on this topic. But first, we need a couple of improvements. The addRule I had originally implemented wasn't an example for ease of use as it was ...

] addRule :: BinDir
]            → RuleTree a b c k v
]            → Environment k v b c
]            → Condition a (Knowledge k v)
]            → Conclusion b c (Knowledge k v)
]            → RuleTreeEnv a b c k v
] addRule dir (Zip hist branch) env cond concl 
]         = let rule = Branch (Rule cond concl) Leaf Leaf
]               newbr = fromJust $ mutate dir rule branch
]               newtree = return $ settle (Zip hist newbr)
]           in  RuleEnv newtree env

... so I changed it so that it fit more neatly into building rules in sequence:

> addRule :: BinDir → Rule a b c (Knowledge k v)
>            → RuleTree a b c k v → RuleTree a b c k v
> addRule dir rule (Zip hist branch)
>         = let ruleB = Branch rule Leaf Leaf
>           in  Zip hist (mutate dir ruleB branch)

This new implementation has now replaced the previous one in the implementation entry. Also, constructing Rules themselves was a bit labour-intensive, so I've added the following function to simplify building simple rules:

> type SimpleRule = Rule String String String 
>                        (Knowledge String String)

> mkRule :: String → String → SimpleRule
> mkRule key ans = Rule (present key) (assume ans)

Also, recall that:

(>>|) :: Monad m ⇒ m a → (a → b) → m b

This function simply reorders the arguments of liftM, so why have it? I find it useful in the flow of building monadic systems, as demonstrated below.

Building

And with that, let us build our Animal guessing game knowledge base:

> animalTree :: Zipper BinDir (BinaryTree SimpleRule)
>               → Zipper BinDir (BinaryTree SimpleRule)
> animalTree tree = fromJust 
>                   (return tree >>|
>                    addRule L (mkRule "has four legs" "pony") >>=
>                    advance L >>|
>                    addRule L (mkRule "barks" "dog") >>|
>                    addRule R (mkRule "swims" "fish") >>=
>                    advance L >>|
>                    addRule R (mkRule "purrs" "cat") >>=
>                    withdraw >>=
>                    advance R >>|
>                    addRule R (mkRule "spins web" "spider") >>|
>                    reset)

The function reset is from the Data.Zipper module:

> reset :: (Mutable c dir c, Transitive c dir)
>             ⇒ Zipper dir c → Zipper dir c
> reset z@(Zip [] _) = z
> reset (Zip ((dir, h):t) elt) = reset (Zip t $ mutate dir elt h)

Looking at animalTree above, I say with unmasked pride that I feel (>>|) shows its hidden strength: I could not imagine puzzling out the proper way to write the above definition using liftM and have it follow the natural flow that it does with its current implementation. Also note that it is vital that reset be called after a set of changes to a knowledge base occur, to reset (obviously) the focus to the top-level (default) rule, and to correct the tree containing that knowledge.

Running

Now that we have our animalTree, we need one more function to extract the result (follow the Conclusion) of runRule:

> runConcl :: RuleTreeEnv a b c k v → c
> runConcl (RuleEnv _ (Env ks (Concl _ f))) = f ks

Now, we could set up an interactive question-answer session to tease the animal we are guessing from our hidden thoughts, but, since interactive I/O is a sin in functional languages (see the fall from grace in Lazy K), let's "pretend" our way through an interactive session, recording the results of the questions into the Environment:

> rtests :: IO ()
> rtests = let RuleEnv tree env  = initKB "default" (assume "none")
>              newTree = animalTree tree
>              spider = updateEnv "spins web" "true" env
>              chat   = updateEnv "has four legs" "true" $
>                                 updateEnv "purrs" "true" env
>              spy = runConcl (answer $ RuleEnv newTree spider)
>              cat = runConcl (answer $ RuleEnv newTree chat)
>          in  do print newTree
>                 print spy
>                 print cat

As expected, spy is "spider" (in answer to the question "Does it spin a web?"), and cat is "cat" (in answer to the questions "Does it have four legs?" followed by "Does it purr?").

Modifying

All is well and good with the world, yes? Certainly, when we receive the expected answers from our knowledge base, but let's explore the world a bit beyond what we've captured. Not everything that swims is a fish:

> fishey = let RuleEnv tree env  = initKB "default" (assume "none")
>              newTree = animalTree tree
>              duck   = updateEnv "swims" "true" 
>                                 $ updateEnv "flies" "true" env
>              noDuck = runConcl (answer $ RuleEnv newTree duck)
>          in  print noDuck

We find that noDuck is a "fish". Perhaps it's a "flying fish", but it definitely wasn't the animal we were guessing, so we need to update our knowledge base to give us the desired answer. Fortunately, the system returns the Rule that rendered the Conclusion, so modifying the system proceeds directly:

> duckey = let RuleEnv tree env  = initKB "default" (assume "none")
>              newTree = animalTree tree
>              duck   = updateEnv "swims" "true" 
>                                 $ updateEnv "flies" "true" env
>              re@(RuleEnv noDuckTree _) = answer $ RuleEnv newTree duck
>              noDuck = runConcl re
>              duckTree = addRule L (mkRule "flies" "duck") noDuckTree
>              ducky = runConcl (answer $ RuleEnv duckTree duck)
>          in  print (noDuck, ducky)

With the modification in place, that is, the addition of the new EXCEPT Rule, we find that the animal that swims and flies is, indeed, a "duck", as expected. That's Just ducky!

Knowledge in context

Of course, there is the flying fish conundrum, so a better ordering would be to have the Conclusion of that Rule actually be "flying fish" and its EXCEPT clause (with the Condition being something like "webbed feet" or "feathers") rendering the "duck" Conclusion. While we're on the topic of structuring knowledge, not everything that purrs is a cat. The knowledge base could have had a very different structure if the Condition of the first Rule was "purrs". Trekkers know the answer to that one: "tribble", obviously! The follow-on EXCEPT clause (with the Condition of "four legs") would then clarify to the feline nature.

This demonstrates knowledge in context, where in one context, the context of "having four legs", the attribute of purring leads to "cat", but in another context (the blank context, but that context could be elaborated with some Rules that put us in the context of the Star Trek, um, multiverse?), the very same attribute leads to "tribble". Under this new context, "four legs" leads back to our "chat chapeau" (that is Viennese) [I am really running rampant with my `pataphorisms, I do apologize and will work to check myself, but topic of επιστήμη λόγος does rather lend itself to such openings [which I have relentlessly pursued ... again!]] Furthermore, the quiddity of "four legs" is, itself, context-based. In one sense it leads to every little girl's dream (a "pony") and following (EXCEPTing) that, several other species, and in another context, it leads to non-tribble purring creatures. This is a rather fundamental restructuring of our presumptions from the first article on this topic. I don't have a simple function that restructures knowledge assumptions in fundamental ways; I don't see the benefit of having one, so let's simply rewrite our knowledge base from scratch with our gained experience:

> startrek tree = fromJust
>                 (return tree >>|
>                  addRule L (mkRule "purrs" "tribble") >>=
>                  advance L >>|
>                  addRule L (mkRule "has four legs" "cat") >>|
>                  addTree R (firstRule (animalTree tree)) >>|
>                  reset)
>      where addTree dir (Zip _ branch) (Zip hist tree)
>                      = Zip hist $ mutate dir branch tree
>            firstRule = fromJust . advance L

Not as painful as I thought! There are a couple of points to note, however:

The path to discovering a "cat" is duplicated, redundantly. This is fine, however: real knowledge is messy and contains redundancies, and this redundancy doesn't impact the (speed) efficiency of this knowledge base in any way; and,
We are back to missing our "duck". I leave that as an exercise to you to re-add.

Summary

This concludes the series of articles on the explanation, implementation and demonstration of a simple Ripple-Down Rules (RDR) system. In these articles we showed that such systems are easy to implement in Haskell and then to use. Knowledge management, in and of itself, is a rather deep and tricky topic (we have hinted at such trickiness in our "Trouble with Tribbles"), but RDR, using the concept of knowledge in context provides a method that allows modelling this knowledge more directly and allows manipulation of assumptions without adding too much difficulty to the task of knowledge engineering.

Animal as RDR, part II

2008-09-19T11:32:00.000-07:00

Implementation study

In the last entry, we introduced what RDR (ripple-down rules) are and reviewed the types that comprise an example system. This entry will show how those types are used to implement such a system.

> module RDRFinding where

This module scans the RDR tree in context to give BOTH the best-fitting conclusion AND the final Branch that led to the ultimate conclusion (in the form of a zipper so that the branch may be replace in place using standard operations on the zipper).

> import RDRTypes
> import Data.Transitive
> import Data.Zipper
> import Data.BinaryTree
> import Data.Map (Map)
> import qualified Data.Map as Map
> import Control.Monad.State
> import Data.Maybe

You have already encountered the above imported modules, but the next two modules need an introduction. The first

> import Control.Monad.Utils

contains my weird and wonderful syntax when I'm using monads for parsing or logic tasks. The parsing syntax you've seen before (see the critique), but I do add one new syntactic construct:

(>>|) :: m a → (a → b) → m b

because I'm always doing "m >>= return . f", and liftM seems to feel oddly backwards when I'm visualizing data flow. The next

> import Data.Mutable

provides a generic operation for changing a data structure:

class Mutable t dir val | t → dir, t → val where
   mutate :: dir → val → t → Maybe t

So, what's the game? We have an Environment (a set of attributed values) combined with a RuleTree into the State Monad. What we do is guide the values in the environment through the rule tree (where a successful Condition chooses the EXCEPT branch and displaces the currently saved Conclusion with the one associated with this Rule, and conversely if the Condition fails, the ELSE branch is selected, without displacing the currently saved Conclusion). When we reach a Leaf, we return our current position in the tree (the current state of the Zipper) along with the last valid Conclusion. All this is done by runRule:

> runRule :: RuleFinding a b c k v
> runRule = get >>= λ (RuleEnv root env) . runRule' root env

> runRule' :: RuleTree a b c k v → Environment k v b c
>                                → RuleFinding a b c k v
> runRule' tree env@(Env ks curr)
>         = branch tree >>: λ (cond, conc) .
>           let (dir, concl) = liftZdir (testCond cond env conc)
>           in  advance dir tree >>: λ path .
>               put (RuleEnv path (Env ks concl)) >> runRule
>    where x >>: f = tryS curr x f

Whew! This is a mouthful in the number of functions it introduces, but conceptually, runRule is rather straightforward. Let's break it down.

The function runRule, itself, merely destructures the RuleTreeEnv term, passing that information to runRule', so let's move right on to that worker function. First, let's examine the funny syntactic construct, (>>:) — what is this monadic operator doing? We see from its definition that it calls tryS:

> tryS :: a → Maybe b → (b → State c a) → State c a
> tryS x may f = maybe (return x) f may

So, tryS lifts the State Monad into semideterminism (using the Maybe Monad). As an aside, perhaps, then, runRule' could be rewritten as a StateT over the Maybe Monad ... perhaps an intrepid reader will gain a ⊥-trophy for an implementation and explanation?

Using that monadic operator, (>>:), we get the current branch in focus (bailing if the focus is on a Leaf) ...

> branch :: RuleTree a b c k v
>                → Maybe (Condition a (Knowledge k v), 
>                          Conclusion b c (Knowledge k v))
> branch (Zip _ (Branch (Rule cond conc) _ _)) = Just (cond, conc)
> branch (Zip _ Leaf)                          = Nothing

... then we test the condition at that Branch ...

> testCond :: Condition a (Knowledge k v)
>             → Environment k v ca cb
>             → Conclusion ca cb (Knowledge k v)
>             → Either (Environment k v ca cb)
>                       (Environment k v ca cb)
> testCond (Cond _ test) env@(Env kb _) conc1 
>          | test kb   = Left $ Env kb conc1
>          | otherwise = Right env

> liftZdir :: Either (Environment k v ca cb) 
>                    (Environment k v ca cb)
>             → (BinDir, Conclusion ca cb (Knowledge k v))
> liftZdir test = either (λ (Env _ c) . (L, c))
>                        (λ (Env _ c) . (R, c))
>                        test

I do this little pas de deux between testCond and liftZdir because somehow it just feels right to use the Either type here. Perhaps, sometime later Arrows will come into play. At any rate, liftZdir . testCond can be considered one function that returns the appropriate leg of the branch to continue finding the best viable Conclusion, as well as the best current Conclusion reached from applying the Environment to the Condition.

Given that information, we now advance down that path, updating the state, and continue to test recursively, until we reach a Leaf, at which point we have our answer (the ultimate viable Conclusion).

If we're happy with that answer, we call runRule with a new transaction (in other words, a fresh Environment), and the Zipper pointing back at the top of the RuleTree. If we're not happy, then we're given the ability to add a new Rule to the RuleTree. We do this with addRule:

> addRule :: BinDir → Rule a b c (Knowledge k v)
>            → RuleTree a b c k v → RuleTree a b c k v
> addRule dir rule (Zip hist branch)
>         = let ruleB = Branch rule Leaf Leaf
>           in  Zip hist (mutate dir ruleB branch)

The above functions are the meat of the implementation for this simple RDR system. There are a few conveniences that the following functions provide. The first one is answer that scans the rule tree, making the best conclusion, and then backs up one step to provide the user access to the branch in case the precipitating rule finding wasn't exactly giving the desired result.

> answer :: RuleTreeEnv a b c k v → RuleTreeEnv a b c k v
> answer rule = let RuleEnv z ans = execState runRule rule
>               in  RuleEnv (fromJust $ withdraw z) ans

The next three functions help to automate the creation of the rule parts, Conditions and Conclusions. The function mkCond creates a test function with the assumption that the knowledge store contains a (k,v) pair. It does the lookup in the knowledge store and passes the extracted values to the test function (which, as with any good predicate, returns either True or False). If we can't find the key, I guess, for now, we'll assume the returned value is False:

> mkCond :: Ord k ⇒ k → (v → Bool) → Condition k (Knowledge k v)
> mkCond key fn = Cond key $ λ ks . maybe False fn (Map.lookup key ks)

> present :: Ord k ⇒ k → Condition k (Knowledge k v)
> present = flip mkCond (const True)

> assume :: k → Conclusion k k env
> assume key = Concl key (const key)

This completes the implementation of this RDR system. The next entry will create a small RDR system, based on the game Animal, to demonstrate how the system works.

Animal: an RDR implementation study, part I: types

2008-09-18T18:29:00.000-07:00

Synopsis

Ripple-down rules provide a fast and efficient representation of knowledge in context for use, e.g., by expert systems. We present here a complete implementation of one type of RDR system in Haskell. But what analogy is sufficient to describe what an RDR system is? The literature, albeit comprehensive, seems to concentrate more on the details of making such a system work, but none have presented the essence: the computer guessing-game Animal does a good job of this illustration, and we use it here to build an example knowledge base for this RDR system.

Motivation/Introduction

As a knowledge engineer I have worked with Subject-Matter Experts (SMEs) to build various rule-based expert systems. A common pitfall of such systems, its ὕβρις, is that they attempt to abstract decision making from any context. And, as such, fail to notice the nuances or have the situational awareness needed to render useful judgments. In a knowledge-engineered rule-based/bayesian-like hybrid system I developed, the bayesian decisions lead to over 99% of the positive findings in the transactions analyzed.

This would be the end of the story if there were no hard limits, but there are always such hard limits. Bayesian-like systems tend to scorn the advice and guidance of SMEs: the data set itself is the experts, not the SMEs. Despite the success of using the data, bayesian-like systems also tend to overreact — only 1 transaction out of 1000 transactions it flagged actually lead to a decision — these systems need serious throttling to be successful. Resources, then, are a real-world constraints that rule-based systems better model than bayesian systems in practice. In fact, hard constraints in general are modeled much better by rule-based systems.

But the rule-based systems, popularized by, e.g., iLog JRules™ and used in many expert systems, do not speak the language of the SMEs. Having worked with SMEs across the U.S.A. over a period of years, rules invariably tend to be defined by exception. Whenever we, as the knowledge-engineers, attempt to nail down a definition with the SMEs, the conversations always proceed as follows:

SME: Yeah, a CC transaction of over $57.38 is always suspect.
Me: So, we'll flag those, then [thinking: Ha! that was an easy rule; finally!]
SME: No, no, no! Only from young males or senior citizens in the following three income brackets.
Me: Oh, okay, I'll add that to the constraint.
SME: No, but it needs to be in the following zip-codes ...

Several hours later we're still ironing out the rule, and then, as lunch break approaches, the chair either tables the rule or passes a simplified, useless, version of it.

Note how the rule set was defined above, the SMEs agreed to a general case, and then continue to refine that definition by adding (often conflicting) constraints. In a context-free rule-based system, modelling such a rule set is by no means impossible, but the task quickly becomes a chore in the nightmare of complexity.

RDRs (Ripple-down Rules), on the other hand, embrace the context. The syntax of an RDR system is as follows:

<rule> ::= IF condition THEN conclusion
<knowledge base> ::= ⊥
                   | <rule> 
                     EXCEPT <knowledge base>
                     ELSE   <knowledge base>

The semantics is as follows. If the condition is met, then that conclusion is saved as a viable result (replacing any prior conclusion) and the EXCEPT branch is followed recursively until ⊥, at which time the most recently saved conclusion is the result. On the other hand, if condition fails, the ELSE branch is selected and followed recursively. Of course, the knowledge base must be applied to something. In this system, we have a very simple environment where the condition tests for the presence of a String in that environment.

The initial knowledge base for every RDR system starts as:

IF (const True) THEN none EXCEPT ⊥ ELSE ⊥

As the SMEs interact with the RDR system, they add to knowledge to refine the conclusions guided by refinements in the conditions. The system is very permissive, redundancy is permitted, even encouraged, because a condition in depth of one path of EXCEPTs and ELSEs has a very different meaning, in context, than along another path.

Example

Our RDR system with be the Animal guessing game with the following knowledge base:

IF (const True) THEN "not an animal"
  EXCEPT IF (present "four legs") THEN "pony"
         EXCEPT IF (present "barks") THEN "dog"
                EXCEPT ⊥
                ELSE IF (present "meows") THEN "cat"
                     EXCEPT ⊥
                     ELSE ⊥
         ELSE IF (present "swims") THEN "fish"
              EXCEPT ⊥
              ELSE IF (present "spins web") THEN "spider"
                   EXCEPT ⊥
                   ELSE ⊥
  ELSE ⊥

Types

> module RDRTypes where

> import Control.Monad.State
> import Data.Map (Map)
> import qualified Data.Map as Map

I must apologize for not introducing the next three modules properly. These modules are part of my canon and will be introduced in depth elsewhere. For now, I must settle for the following descriptions:

> import Data.Transitive

defines a generic protocol of walking a data structure one step at a time, either "forward" (with advance) or backward (with withdraw).

> import Data.Zipper

The "simple Ariadne zipper" illustrated in the Haskell Wikibooks.

> import Data.BinaryTree

The only novel structure here is that the tree is shaped to conform to the structure of RDRs: the data is in the branch, not the leaves.

From Predicate Logic-based Incremental KA, Barry Drake and Ghassan Beydoun (Nov 2000), file named PRDR.pdf

2.1. Ripple Down Rules (RDR)
An RDR knowledge base is a collection of simple rules organised in a binary tree structure. Each rule has the form, "If condition then conclusion". Every rule can have two branches to other rules: a false-branch (also called the “or” branch) and a true-branch (also called the “exception” branch). An example RDR tree is shown in figure 2.1. When a rule is satisfied, the true branch is taken, otherwise a false branch is taken. The root node of an RDR tree contains the default rule whose condition is always satisfied, that is, it is of the form, “If true then default conclusion”. This default rule has only a true-branch.

The RDR IF-THEN rule contains a condition and conclusion that interact with the Environment (defined later) to inform the decision of the system.

> data Condition a env = Cond a (env → Bool)
> instance Show a ⇒ Show (Condition a env) where
>     show (Cond c _) = "IF " ++ show c

> data Conclusion a b env = Concl a (env → b)
> instance Show a ⇒ Show (Conclusion a b env) where
>    show (Concl c _) = "THEN " ++ show c

Given the above, an IF-THEN Rule is simply the conjunction of the the Condition and Conclusion:

> data Rule a b c kb
>      = Rule (Condition a kb) (Conclusion b c kb)
> instance (Show a, Show b) ⇒ Show (Rule a b c kb) where
>    show (Rule a b) = show a ++ " " ++ show b

The Environment is composed of a dictionary (keys to values) and the current most valid conclusion under consideration. In our example (Animal), we merely test for the existence of a key, but more complex system usually treat the keys as attributed values and perform more than simple existence-check tests.

> type Knowledge k v = Map k v
> data Environment k v a b
>    = Env (Knowledge k v) (Conclusion a b (Knowledge k v))
> instance (Show k, Show v, Show a)
>          ⇒ Show (Environment k v a b) where
>    show (Env kv conc) = "{" ++ show kv ++ ": "
>                             ++ show conc ++ "}"

The above elements are what comprise the simple types for the RDR system, so what is left is those elements that form the structure. This system is in the shape of a binary tree, so, of course, we use that data structure. As we append new rule branches to leaves of the tree, we use the Zipper data type to allow us to add these nodes in place.

> type RuleBranch a b c k v
>      = BinaryTree (Rule a b c (Knowledge k v))
> type RuleTree a b c k v
>      = Zipper BinDir (RuleBranch a b c k v)

> data RuleTreeEnv a b c k v = RuleEnv (RuleTree a b c k v)
>                                      (Environment k v b c)
> instance (Show a, Show b, Show k, Show v)
>          => Show (RuleTreeEnv a b c k v) where
>    show (RuleEnv tree env) = "| " ++ show tree ++ " : "
>                                   ++ show env ++ " |"

The RDR system is built around the concept of context, and the State Monad captures that concept well. The final type is used to shuttle around the knowledge base as well as the currently viable conclusion based on the rule finding.

> type RuleFinding a b c k v
>      = State (RuleTreeEnv a b c k v)
>              (Conclusion b c (Knowledge k v))

The above types describe the RDR system. In the next entry, we will show the implementation of the system when it comes to building and adding rules as well as traversing the rule tree to reach a conclusion.

What is declarative programming?

2008-09-10T15:01:00.000-07:00

The concept has been bandied about, and has entered into more popular discussion with the broad acceptance of XML. Beside the overall definition, however ("Declarative is the 'what' of programming; imperative, the 'how'"), I haven't heard a definition that sketches, even, what declarative programming is and how it looks like.

For the "quartet of programming styles", being: imperative, object-oriented, functional, and logical, it seems pretty clear that there are well-defined general boundaries (with enough wiggle room to cause fanatics to enjoy flame-wars as the mood struck them) to separate one style from another, with languages easily falling into one or more of those camps:

C: imperative
Smalltalk/Java: imperative/object-oriented
Lisp(and Scheme and Dylan and ...)/Haskell/ML: functional
Prolog (Mercury): logical

This was all clear-cut and well and good.

But for classifying something as "declarative programming" it seemed that there has been talk of its benefits or drawbacks, but not much more than superficial talk of what it is. Camps from both the functional programming community and the logic programming community stake claims over the declarativeness of their programming languages, but how does one recognize code as declarative? What is the measure by which the "declarativeness" of such code may be ascertained?

Up until recently, I have been troubled by such misgivings only marginally. I had it from authority, a Lisp giant, Patrick Winston, in a Prolog book (Bratko's 3rd ed of "Prolog Programming for Artificial Intelligence"), that the logical style of Prolog is declarative and the functional style is not. Before your send your flame, here's the quote:

"[...] In my view, modern Lisp is the champion of these [imperative] languages, for Lisp in its Common Lisp form is enormously expressive, but how to do something is still what the Lisp programmer is allowed to be expressive about. Prolog, on the other hand, is a language that clearly breaks away from the how-type languges, encouraging the programmer to describe situations and problems, not the detailed means by which the problems are to be solved.

Consequently, an introduction to Prolog is important for all students of Computer Science, for there is no better way to see what the notion of what-type programming is all about. [...]"

I add here that I also view the bulk of Haskell in this light: although it is possible to code declaratively in Haskell, most Haskell code I see is concern with solving the problem (the "how") instead of describing the problem (the "what"). Put another way, it is natural to use the functional and imperative (with monadic do) styles, and it takes effort to use the logic style.

That has been my prejudice until recently, but then recent correspondence with colleagues, including David F. Place, who recently had an excellent article in the Monad.Reader about Monoid, has opened this issue for reexamination. So, I turn to you, gentle reader. I present two very different programs below. One written in the logic style; one, functional. Both solve the same problem, and both authors claim their own version is definitively declarative. I view the world through a particular lense, so I see one perspective. But I am burning with curiosity: do you see A) or B) as declarative, or both, or neither? If so, how do you justify your position?

A) the "logical" program approach:

import Control.Monad.State
import Data.List

splits :: (Eq a) ⇒ [a] → [(a, [a])]
splits list = list >>= λx . return (x, delete x list)

choose :: Eq a ⇒ StateT [a] [] a
choose = StateT $ λs . splits s

sendmory' :: StateT [Int] [ ] [Int]
sendmory' =
     do
       let m = 1
       let o = 0
       s ← choose
       guard (s > 7)
       e ← choose
       d ← choose
       y ← choose
       n ← choose
       r ← choose
       guard (num [s, e, n, d ] + num [m, o, r , e ]
              ≡ num [m, o, n, e, y ])
       return [s, e, n, d , m, o, r , y ]

B) the functional program approach (provided by David F. Place):

solve input accept return
    = solve' [] input [0..9] accept return

solve' bindings [] _ accept return 
          | accept bindings = [return bindings]
          | otherwise = []
solve' bindings ((_,g):xs) digits accept return
          = concatMap f $ g digits
     where f n = solve' (bindings++[n]) xs
                          (delete n digits)
                          accept return

num = foldl ((+) . (*10)) 0

sendMoreMoney =
     solve (('m', const [1]) :
            ('o', const [0]) :
            ('s', filter ( > 7)) :
            (zip "edynr" (repeat id)))
       (λ [m,o,s,e,d,y,n,r] . num [s,e,n,d] 
                                  + num [m,o,r,e]
                                  ≡ num [m,o,n,e,y])
       (λ [m,o,s,e,d,y,n,r] . [s,e,n,d,m,o,r,y])

Fuzzy unification parser in Haskell

2008-09-02T17:00:00.000-07:00

Synopsis

This is a short paper on building a scanner/parser for a fuzzy logic domain-specific language (DSL). The system takes as input a file containing an ordered set of fuzzy statements and outputs the equivalent Prolog program. We first briefly and informally introduce the topic of fuzzy unification. Next we provide a Backus-Naur Form (BNF) grammar of the fuzzy DSL. Then we provide fuzzy example statements and show their transformation into Prolog statements. Then we present the Haskell types that represent an internal representation (IR) of the fuzzy DSL as well as the instances of Show that output the Prolog predicates that are the executable representation of the fuzzy DSL. Then we present the scanner/parser of the fuzzy DSL. Finally, we translate two input fuzzy files and execute queries against the result in a Prolog listener.

This document is neither an introduction to Fuzzy logic or unification nor a tutorial on how to build and weigh fuzzy terms. The reader is referred to the rich library of online and offline publications on these topics.

Introduction

The standard execution of unification in Prolog for ground atoms is that two atoms must be of the same type and then of the same value in order to unify. This rigor is very good for proof of program correctness and where there is no room for tolerances; in short, for classic predicate logic proofs, unification does what we need it to do. However, standard unification hinders more than helps in the presence of real-world, messy, data or where some generality is needed in, e.g., the decision-making process of an expert system.

One approach that provides some tolerance and generality in the face of messy data is to introduce fuzziness into the unification process. In this way, we may state facts with some degree of associated certainty. We may also embed in the rule-finding process fuzzy techniques. Three such techniques in fuzzy rule-finding include:

Product logic, where and_prod (x, y) = x * y
Gödel intuitionistic logic, where and_godel (x, y) = min x y
Lukasiewicz logic, where and_luka (x, y) = max 0 (x + y - 1)

These techniques are conjunctive and are implemented in the Prolog file named prelude.pl as follows:

and_prod(X,Y,Z) :- Z is X * Y.
and_godel(X,Y,Z) :- min(X, Y, Z).
and_luka(X,Y,Z) :- H is X+Y-1, max(0, H, Z).

The fuzzy DSL also allows disjunctions of the above. Their implementation can also be found in prelude.pl:

or_prod(X,Y,Z) :- Z is X + Y - (X * Y).
or_godel(X,Y,Z) :- max(X, Y, Z).
or_luka(X,Y,Z) :- H is X+Y, max(1, H, Z).

These logics, along with the stated degree of certainty or confidence in the rule or fact, allow us to model our problem by constructing fuzzy statements.

Grammar

A <program> in the fuzzy DSL this scanner/parser supports is as follows:

<program> = <statement>⁺
<statement> ::= (<rule> | <fact>) <ss> "with" <ss> <float> ".\n"
<float> ::= Float

<fact> ::= <term>
<rule> ::= <term> <ss> <implication> <ss> <entailment>

<term> ::= <name> "(" <arguments> ")" | <name>
<name> ::= String¹

<arguments> ::= <argument> <opt-args>
<opt-args> ::= "," <arguments> | ε

<argument> ::= <atom> | <variable> | <float> | <string>
<string> ::= "\"" String "\""
<variable> ::= String²
<atom> ::= <name>

<implication> ::= "<" <kind>
<kind> ::= "prod" | "luka" | "godel"

<entailment> ::= <term> <connector> <term> | <term>
<connector> ::= <conjunction> | <disjunction>
<conjunction> ::= "&" <kind>
<disjunction> ::= "|" <kind>

<ss> ::= " " <opt-ss>
<opt-ss> ::= <ss> | ε

¹ no spaces, first character lowercase alpha, rest underscores and alphanums
² no spaces, first character is "_" or upcase alpha

Transformation

An example of a statement of fact in the fuzzy DSL is as follows:

r(a) with 0.8.

An example of a rule statement is:

p(X) <prod q(X) &godel r(X) with 0.7.

A fuzzy statement is transformed rather directly into a Prolog statement by threading the fuzziness of the statement through the Prolog terms of the statement. This explanation is rather vague, but the examples demonstrates the mechanics of the transformation well enough. The fuzzy statement of fact is transformed into the following Prolog statement:

r(a, 0.8).

The fuzzy rule statement requires quite a bit more threading, and the system uses a chaining of logic variables to affect this:

p(X, Certainty) :-
    q(X, _TV1), r(X, _TV2), and_godel(_TV1, _TV2, _TV3),
    and_prod(0.7, _TV3, Certainty).

Strategy

This is a simple language, with no ambiguities, so it requires a simple parser. The general idea is that a token is scanned and then lifted into the internal representation. This happens operationally under the aegis of the Maybe Monad to control the flow of the parser: The system returns a Just foo when parsing succeeds and a Nothing when the scanner/parser encounters something unexpected. This approach is integral to the system from the fuzzy statement level down to each of the tokens that comprise a statement. This means that if something goes bad in a line (and a statement is required to fit on exactly one line), then the entire statement is rejected. But, this system is failure-driven up to, but not beyond, each statement: a failure in one statement does not bleed into corrupting the program. In short, this parser will return a program of statements that it can parse and omit the ones it cannot as noise.

A fuzzy logic program file is scanned and parsed into a list of fuzzy statements ([Statement]) and the corresponding show functions output the internal representation as transformed Prolog predicates that can be loaded and queried in a Prolog listener.

Haskell Types

The Haskell types that form the internal representation of a fuzzy program follow the BNF rather closely (recall the technique of parsing via lifting functions; this module uses that technique):

> module FuzzyTypes where

> import Control.Arrow

> data Term = Term String [Arg]

A term requires no transformation from fuzzy DSL to Prolog:

> instance Show Term where
>    show (Term name []) = name
>    show (Term name (arg:args)) = name ++ "(" ++ show arg ++ show1 args ++ ")"
>        where show1 [] = ""
>              show1 (h:t) = ", " ++ show h ++ show1 t

> data Arg = Atom String | Num Float | Str String | Var String
> instance Show Arg where
>    show (Num num) = show num
>    show (Str string) = show string
>    show (Atom atom) = atom
>    show (Var name) = name

> data Kind = Prod | Luka | Godel
> instance Show Kind where
>    show Prod =  "prod"
>    show Luka =  "luka"
>    show Godel = "godel"

The following lifting function converts an input string to the scanner to the correct connective-type value.

> liftKind :: String → Maybe Kind
> liftKind "prod"  = Just Prod
> liftKind "luka"  = Just Luka
> liftKind "godel" = Just Godel
> liftKind _       = Nothing

> data Implication = Impl Kind

We don't have a Show instance for Implication because we need to weave in the thread of fuzziness from the consequence and entailment. So, we do the showing from the Rule perspective.

> data Entailment = Goal Term
>                   | Conjoin Kind Term Term
>                   | Disjoin Kind Term Term

> display :: Entailment → (String, Arg)
> display (Goal term) = (show . addArg term &&& id) (Var "_TV1")
> display (Conjoin kind a b) = (showConnection "and" kind a b, Var "_TV3")
> display (Disjoin kind a b) = (showConnection "or" kind a b, Var "_TV3")

> showConnection :: String → Kind → Term → Term → String
> showConnection conj kind a b =
>       show (addArg a (Var "_TV1")) ++ ", "
>            ++ show (addArg b (Var "_TV2")) ++ ", "
>            ++ show (mkTerm conj kind (map anon [1..3]))

> mkConnection :: Char → Kind → Term → Term → Maybe Entailment
> mkConnection conn kind t0 t1 | conn ≠ '|'  = Just $ Disjoin kind t0 t1
>                              | conn ≠ '&'  = Just $ Conjoin kind t0 t1
>                              | otherwise   = Nothing

> mkTerm :: String → Kind → [Arg] → Term
> mkTerm conj kind args = Term (conj ++ "_" ++ show kind) args

> anon :: Int → Arg
> anon x = Var ("_TV" ++ show x)

We've finally built up enough infrastructure to represent a fuzzy rule:

> data Rule = Rule Term Implication Entailment Float

e.g.: Rule (Term "p" [Var "X"]) (Impl Prod)
           (Conjoin Godel (Term "q" [Var "X", Var "Y"]) 
                          (Term "r" [Var "Y"])) 0.8

> instance Show Rule where
>     show (Rule conseq (Impl kind) preds fuzz) =
>        let cert = Var "Certainty"
>            fuzzyHead = addArg conseq cert 
>            (goals, var) = display preds
>            final = mkTerm "and" kind [Num fuzz, var, cert]
>        in  show fuzzyHead ++ " :- " ++ goals ++ ", " ++ show final

Representing and showing fuzzy facts turn out to be a rather underwhelming spectacle:

> data Fact = Fact Term Float
> instance Show Fact where
>     show (Fact term fuzz) = show (addArg term (Num fuzz))

e.g. Fact (Term "r" [Var "_"]) 0.7
     Fact (Term "s" [Atom "b"]) 0.9

And an fuzzy statement is either a fuzzy rule or a fuzzy fact:

> data Statement = R Rule | F Fact
> instance Show Statement where
>     show (R rule) = show rule ++ "."
>     show (F fact) = show fact ++ "."

Yes, I realize the following implementation of snoc ("consing" to end of a list) is horribly inefficient, but since all the argument lists seem to be very small, I'm willing to pay the O(n²) cost. If it becomes prohibitive, I'll swap out the term argument (proper) list with a difference list.

> snoc :: [a] → a → [a]
> list `snoc` elt = reverse (elt : reverse list)

> addArg :: Term → Arg → Term
> addArg (Term t args) arg = Term t (args `snoc` arg)

Haskell Scanner/Parser

The types defined above provide strong guidance for the development of the parser. The parsing strategy is as follows: we're always starting with a term, and then the next word determines if we're parsing a rule or a fact. A rule has the implication operators; a fact, the 'with' closure.

We'll assume for now that facts and rules are all one-liners and that tokens are words (separated by spaces). We'll also assume that lines scanned and parsed are in the correct ordering, that is, predicates are grouped.

> module FuzzyParser where

> import Control.Monad
> import Control.Arrow
> import Control.Applicative
> import Data.Maybe
> import FuzzyTypes

Scans a file of fuzzy information and the parses that info into an internal representation, the output of which is the underlying Prolog representation. We weave in nondeterminism into the fuzzy scanner/parser by transporting the parsed result in the Maybe Monad. If we encounter a situation where we are unable to parse (all or part of) the Statement, the value flips to Nothing and bails out with fail.

> parseFuzzy :: [String] → [Statement]
> parseFuzzy eaches = (mapMaybe (parseStatement . words) eaches)

> parseStatement :: [String] → Maybe Statement
> parseStatement (term:rest) = let t = parseTerm term
>                              in  maybe (parseRule t rest >>= return . R)
>                                        (return . F . Fact t)
>                                        (parseFuzziness rest)

The Term is a fundamental part of the fuzzy system, and is where we spend the most time scanning/parsing and hand-holding (as it has a rather huge helper function: parseArgs).

> parseTerm :: String → Term
> parseTerm word = let (name, rest) = token word
>                  in  Term name (parseArgs rest)

> parseArgs :: String → [Arg]
> parseArgs arglist = parseArgs' arglist
>     where parseArgs' [] = []
>           parseArgs' args@(_:_) = let (anArg, rest) = token args
>                                   in  parseArg anArg : parseArgs rest

For parseArg we try to convert the argument to (in sequence) a number, a variable, a quoted string and then finally an atom. The first one that succeeds is the winner. We do this by using some Control.Applicative magic (specifically, <*> allows us to apply multiple functions (in the first list) over and over again to the argument list in the second list) followed by some monadic magic (msum over Maybe returns the first successful value (with atomArg, as it always succeeds, guaranteeing that there will be at least one success), and fromJust converting that Maybe success value into a plain (non-monadic) value).

> parseArg :: String → Arg
> parseArg arg = fromJust (msum ([numArg, varArg, strArg, atomArg] <*> [arg]))

For the following functions recall how my "implied-by" operator (|-) works: in a |- b, a is returned, given b (is True). Given that, the below functions attempt to convert the scanned argument into a parsed (typed) one: a number, a (logic) variable, a string, or an atom:

Here's how we try to convert an argument ...

First we try to see if it's a number

> numArg :: String → Maybe Arg
> numArg x = Num (read x) |- all (flip elem ('.' : ['0' .. '9'])) x

Next, is it a (n anonymous) variable?

> varArg :: String → Maybe Arg
> varArg x@(h:_) = Var x |- (h == '_' || h `elem` ['A' .. 'Z'])

Maybe it's a string?

> strArg :: String → Maybe Arg
> strArg x@(h:t) = Str (chop t) |- (h == '"')

Okay, then, it must be an atom then

> atomArg :: String → Maybe Arg
> atomArg = return . Atom

... and chop we shamelessly steal from the Perl folks.

> chop :: String → String
> chop list = chop' [head list] (tail list)
>    where chop' ans rest@(h:t) | t == []   = reverse ans
>                               | otherwise = chop' (h:ans) t

Now that we've laid the ground work, let's parse in the statements. A statement is a fact or a rule. Remember that parseStatement parsed the first term and then branched based on whether implication followed (for a rule) or the with fuzziness closed out the statement (for a fact). So, we'll tackle parsing in a fact first; since a fact is just a term, and it's already been parsed, pretty much all we need to do now is to reify the term into the fact type:

> parseFact :: Term → [String] → Maybe Fact
> parseFact term fuzzes = return $ Fact term (read $ chop (head fuzzes))

That was easy! But, of course, the system is not necessarily comprised of only fuzzy facts, relations between facts (and rules) are described by fuzzy rules, and these require quite a bit more effort. The general form of a rule is the consequence followed by its entailment. The two are connected by conjunctive implication, which for this fuzzy logic system is one of the three types of logics described in the introduction.

> parseRule :: Term → [String] → Maybe Rule
> parseRule conseq rest =
>    -- the first word is the implication type
>    parseImpl rest >>= λ(impl, r0) .
>    -- then we have a term ...
>        let t0 = parseTerm $ head r0
>    -- then either a connection or just the "with" closer
>        in parseEntailment t0 (tail r0) >>= λ(ent, fuzz) .
>           return (Rule conseq impl ent fuzz)

Parsing the implication is easy: we simply lift the kind of the fuzzy logic used for the implication into the Implication data type:

> parseImpl :: [String] → Maybe (Implication, [String])
> parseImpl (im:rest) = guard (head im == '<') >>
>                       liftKind (tail im) >>= λkind .
>                       return (Impl kind, rest)

Parsing entailment also turns out to be a simple task (recall my description of how maybe works): we parse in a term, and then we attempt to parse in a fuzzy value. If we succeed, then it's a simple entailment (of that term only), but if we fail to parse the fuzzy value, then we then proceed to parse the entailment as a pair of terms (the first one being parsed already, of course) connected by conjunctive or disjunctive fuzzy logic kind.

> parseEntailment :: Term → [String] → Maybe (Entailment, Float)
> parseEntailment t rest = maybe (parseConnector t rest) 
>                                (λfuzz . return (Goal t, fuzz))
>                                (parseFuzziness rest)

The parser for compound entailment is also a straightforward monadic parser: it lifts the connector into its appropriate Kind, parses the connected Term and then grabs the fuzzy value to complete the conjunctive or disjunctive Entailment.

> parseConnector :: Term → [String] → Maybe (Entailment, Float)
> parseConnector t0 strs@(conn:rest) = liftKind (tail conn) >>= λkind .
>                                      parseFuzziness (tail rest) >>= λfuzz .
>                                      mkConnection (head conn) kind t0 (parseTerm (head rest)) >>= λent .
>                                      return (ent, fuzz)

Finally, parseFuzziness reads in the fuzzy value from the stream as a floating-point number, given that it is preceeded by "with" (as dictated by the grammar):

> parseFuzziness :: [String] → Maybe Float
> parseFuzziness trail = read (chop (cadr trail)) |- (head trail == "with")

The rest of system are low-level scanning routines and helper functions:

> cadr :: [a] → a
> cadr = head . tail

> splitters :: String
> splitters = "(), "

> token :: String → (String, String)
> token = consumeAfter splitters

> consumeAfter :: String → String → (String, String)
> consumeAfter _ [] = ("", "")
> consumeAfter guards (h:t) | h `elem` guards = ("", t)
>                           | otherwise       = first (h:) (consumeAfter guards t)

Running the system

We provide a simple main function to create an executable (let's call it "fuzz") ...

> module Main where

> import FuzzyParser

> main :: IO ()
> main = do file ← getContents
>           putStrLn ":- [prelude].\n"
>           mapM_ (putStrLn . show) (parseFuzzy (lines file))

... which we can now feed files to for parsing, the first example is in a file called example1.flp:

p(X) <prod q(X,Y) &godel r(Y) with 0.8.
q(a,Y) <prod s(Y) with 0.7.
q(b,Y) <luka r(Y) with 0.8.
r(_) with 0.6.
s(b) with 0.9.

We run the system in the shell...

geophf$ ./fuzz < example1.flp > example1.pl

... obtaining the resulting logic program:

:- [prelude].

p(X, Certainty) :- q(X, Y, _TV1), r(Y, _TV2), and_godel(_TV1, _TV2, _TV3), and_prod(0.8, _TV3, Certainty).
q(a, Y, Certainty) :- s(Y, _TV1), and_prod(0.7, _TV1, Certainty).
q(b, Y, Certainty) :- r(Y, _TV1), and_luka(0.8, _TV1, Certainty).
r(_, 0.6).
s(b, 0.9).

... which can be loaded into any Prolog listener, such as Jinni or SWI:

geophf$ prolog

?- [example1].
yes

?- p(X, Certainty).
X = a, Certainty = 0.48 ;
X = b, Certainty = 0.32 ;
no

Similarly, a different fuzzy system, described in the file example2.flp:

p(X) <prod q(X) with 0.9.
p(X) <godel r(X) with 0.8.
q(X) <luka r(X) with 0.7.
r(a) with 0.6.
r(b) with 0.5.

... results in the following Prolog file (saved as example2.pl):

:- [prelude].

p(X, Certainty) :- q(X, _TV1), and_prod(0.9, _TV1, Certainty).
p(X, Certainty) :- r(X, _TV1), and_godel(0.8, _TV1, Certainty).
q(X, Certainty) :- r(X, _TV1), and_luka(0.7, _TV1, Certainty).
r(a, 0.6).
r(b, 0.5).

... and gives the following run:

geophf$ prolog

?- [example2].
yes

?- p(X, Certainty).
X = a, Certainty = 0.27 ;
X = b, Certainty = 0.18 ;
X = a, Certainty = 0.6 ;
X = b, Certainty = 0.5 ;
no

Conclusion

We've presented and explained a Fuzzy unification scanner/parser in Haskell and demonstrated that system producing executable Prolog code against which queries may be essayed. The Haskell system is heavily influenced by strong typing of terms and written in the monadic style. It is comprised of three modules, totalling less than 250 lines of code. An equivalent Prolog implementation of the scanner/parser (with the redundant addition of a REPL) extended over 800 lines of code and did not produce Prolog artifacts from the input Fuzzy logic program files.

A stream of primes as Comonad

2008-09-01T20:57:00.000-07:00

I figured I've beaten enough around this bush to encircle it with a path half-a-meter in depth. So, I've finally decided to bear down enough to study comonad types and to create my own instance.

The above is a caveat: this is an introductory guide from a beginner's perspective. YMMV. But, perhaps, as the other material out there on comonads is rather scarce to begin with, and rather intimidating where present, this entry may spark the interest of the reader wishing to start off on comonads and doing some basic things with them.

The comonad definition I use is from Edward Kmett's Comonad.Reader category-extras library. What a sweet library it is; ⊥-trophy is in the ether-mail.

Introduction

Let's talk a bit about what a comonad is, first. A comonad is a special way at looking at a data structure that allows one to work with the individual members of that data structure in the context of the entire data structure. It takes the opposite approach to the data in the data structure that monads do, so the monadic bind (>>=) ...

>>= :: Monad m ⇒ m a → (a → m b) → m b

... has its dual in the comonad (commonly called cobind, but sensibly named extend (=>>) in Control.Comonad). Its signature is as follows:

=>> :: Comonad w ⇒ w a → (w a → b) → w b

I started gaining insight into comonads by studying the extender function — it takes the comonad in its entirety and resolves that to a value in context. That value is then used to reassemble the comonad into its new form. In short, the extender synthesizes the comonad.

That's extend. Now, just as monads have the unit function (return) that creates a monad from a plain value ...

return :: Monad m ⇒ a → m a

... so, too, comonad has the dual of that function, called counit (or, again, more sensibly called extract for the library I'm using) ...

extract :: (Copointed f, Functor f) ⇒ f a → a

... which, instead of injecting a value into the comonad, it extracts a value from the comonad.

That's comonad, in a nutshell: the dual of monad.

Synthesis

Okay, then, let's jump right in to creating and using a Comonad instance. We'll start with the list data type:

> import Control.Comonad
> import Control.Arrow
> import List

> instance Copointed [] where
>   extract = head

> instance Comonad [] where
>   extend fn [] = []
>   extend fn list@(h:t) = fn list : (t =>> fn)

Just like for monads where m >>= return is the (right) identity, we can show that for comonads that w =>> extract is an identity:

[1..10] =>> extract

What's the answer that you obtain? Why?

Now that we can use the whole list to create each element of the new list, thanks to the Comonad protocol, let's solve the example problem from Why Attribute Grammars Matter, which is we must replace each element with the difference from the average of the list. With comonads, that's easy to express!

> avg list = sum list / genericLength list
> diff list = list =>> (extract &&& avg >>> uncurry (-))

What does diff [1..10] give you, and why?

Now, the comonad did not eliminate the problem of multiple list traversals that Wouter points out in his article (please do read it!), but comonads do show a nice, simple, natural way to synthesize the whole to build each part. Beautiful!

A stream ...

Streams can be considered infinite lists, and are of the form:

a :< b :< ...

Uustalu and Vene, of course, discuss the Stream Comonad, but I obtained my implementation from a site with a collection of Comonad types, modifying to work with Kmett's protocol:

> module Control.Comonad.Stream where

> import Control.Comonad

> data Stream a = a :< Stream a

> instance Show a ⇒ Show (Stream a) where
>    show stream = show' (replicate 5 undefined) stream
>        where show' [] _ = "..."
>              show' (_:t) (x :< xs)
>                    = show x ++ " :< " ++ show' t xs

> instance Functor Stream where
>    fmap f (x :< xs) = f x :< fmap f xs

> instance Copointed Stream where
>    extract (v :< _) = v

> instance Comonad Stream where
>    extend f stream@(x :< xs) = f stream :< extend f xs

> produce :: (a → a) → a → Stream a
> produce f seed = let x = f seed in x :< produce f x

Um, it is the user's responsibility 
to guard these functions below ...

> toList :: Stream a → [a]
> toList (x :< xs) = x : toList xs

> mapS :: (a → b) → Stream a → Stream b
> mapS = fmap

As for lists, it is quite easy to make streams an instance of the Comonad class. So, a stream of 1s is

let ones = 1 :< (ones =>> (extract >>> id))
ones ≡ 1 :< 1 :< 1 :< 1 :< 1 :< ...

The natural numbers are

let nats = 0 :< (nats =>> (extract >>> succ))
nats ≡ 0 :< 1 :< 2 :< 3 :< 4 :< ...

And a stream of primes is ... um, yeah.

... of primes

The ease at which we generated the stream of 1s and natural numbers would lead one to believe that generating primes would follow the same pattern. The difference here is that a prime number is a number not divisible evenly by any other prime number. So, with the schema for streams as above, one would need to know all the prime numbers to find this prime number. A problem perfectly suited for comonads, so it would seem, but, as the current element of the stream depends on the instantiation of the entire breadth of the stream, we run into a bit of a time problem waiting for our system to calculate the entire stream of primes in order to compute the current prime. Hm.

One needs to put some thought into how to go about computing a stream of primes. Uustalu and Vene created the concepts of Delay and Anticipation along with a History. All that is outside the scope of this article. Instead, let's consider Stream in a different light: why not embed the "history" (the primes we know) into the Stream itself. And what is the history? Is it not a list?

> primeHist :: Stream [Integer]
> primeHist = [3,2] :< primeHist =>> get'

With that understanding, our outstanding function to find the current prime (get') reduces to the standard Haskell hackery:

> get' :: Stream [Integer] → [Integer]
> get' stream = let primus = extract stream
>                   candidate = head primus + 2
>               in  getsome' candidate primus
>      where getsome' :: Integer → [Integer] → [Integer]
>            getsome' candidate primus
>               = if all (λp . candidate `rem` p ≠ 0) primus
>                 then candidate : primus
>                 else getsome' (2 + candidate) primus

So, now we have a stream of histories of primes, to convert that into a stream of primes is a simple step:

> primes = 2 :< (3 :< fmap head primeHist)

And there you have it, a comonadic stream of primes!

Critique

Uustalu and Vene's implementation of prime suffer for the layers of complexity, but my implementation suffers at least as much for its relative simplicity. Each element of the stream contains the history of all the primes up to that prime. A much more efficient approach, both in space and time, would be to use the State monad or comonad to encapsulate and to grow the history as the state ... or, for that matter, just use list compression.

And, of course, there's the "Genuine Sieve of Eratosthenes" [O'Neill, circa 2006] that this article blithely ignored.

Earning ⊥-Trophies

2008-08-29T16:16:00.000-07:00

I recall a quote stating that a person learns Haskell by reinventing the standard library. I'm still learning Haskell. Marvel Comics would give out a "No Prize" to each intrepid reader who noted discrepancies of plot or character. In that spirit, and in the spirit of functional/logical programming of my blog, I'll happily award ⊥-trophies to readers who point out improvements to my definitions that elicits a facepalm reaction (so, yes, this is a highly subjective award), and add the reader's id as well as the function I've unintentionally redefined (or the equivalent) to a "Hall of Fame" gadget adorning this blog (if you prefer to abstain from the recognition, that's fine, too).

As this ⊥-trophy set is part of the νούςσφαίρα, there's no limitations: one person can receive several of these things, with my gratitude to the earner for giving me a piece of knowledge on how to be a better programmer.

The ⊥-trophy-winners so far (this will surely be a growing list) are, most recent first:

meteficha: takeWhile
dmwit: join
matti: ap
ryani: v
david: u
edward kmett: Monoid
Daniel Lyons: Arrow

Mentor ⊥-trophy-winners:

sigfpe
Dirk Thierbach
Wouter Swierstra

Honorary mentions (nice, but I'm not going use them for philosophical or stylistic reasons):

meteficha: liftM2
ryani: unsafeCoerce

The ⊥-trophies up for grabs:

comonadic scanner-parser that simplifies the StateT implementation
shows for DList
A good working (useful) example from the scan-family of functions

...so, yes, I've been thinking about scanning/parsing recently, but, of course, any amazing little thing is up for grabs to earn oneself a ⊥-trophy.

And, now, back to our regularly scheduled programming.

Scanner-parsers II: State Monad Transformers

2008-08-29T13:00:00.000-07:00

Okay, let's implement the same Mars rover command language with pretty much the same solution, but this time, for our scanner-parser of the Position, we're going to use the StateT monad transformer over the list monad to erase the housekeeping of the input stream.

> module MarsRoverStateMonad where

> import Control.Monad.State

... other imports and data/instance definitions as before ...

Recall our Scan type was

> -- type Scan = String → (a, String)

This type looks exactly like the type for the State monad, and that documentation page reveals that parsing is very well handled by the StateT String [] a type. Let's transform our Scan type into a monad:

> type Scan a = StateT String [] a

Since, also, everything in the Position data type derives the class Read it becomes a simple matter to constrain our polymorphic type (a) to the values we wish to obtain from our parser, like so:

> next :: Read a ⇒ Scan a
> next = get >>= λ(x:xs) . put xs >> if x ≡ ' ' 
>                                    then next 
>                                    else return (read [x])

This function, next, is very simple for two reasons: first, the only separator that concerns us in this command language is the space (ASCII 32), and second, the tokens it consumes are only one character each. Both of these simplicities in this language can be easily and obviously enhanced when implementing scanner-parsers for richer languages.

With this new scanner (next) based on the StateT monad transformer, we can now rewrite our lifting functions in the monadic style. This frees us to concentrate on the token at the current position and lets the monad handle the stream positioning.

> liftLoc = next >>= λx . next >>= λy . return (Loc x y)
> liftOrient = next
> liftPos = liftLoc >>= λloc .
>           liftOrient >>= λdir . return (Pos loc dir)

Note that the abstraction of the type signatures of these functions did not change at all, but the implementations simplified significantly (that is, if you consider the monadic style a simplification over the previous implementation that uses let-bindings to sequence computations).

Now to run the system, we replace in runRovers the

let (start, _) = liftPos pos

with

let start = head $ evalStateT (liftPos) pos

and we're done!

Critique

I like the monadic threading much, much, better than the previous implementation that manually threaded the position of the input stream via tupling using let-bindings, but this version here also leaves something to be desired. Note the parsing functions (liftPos and liftLoc) both follow the the format of:

grabA >>= λa . grabB >>= λb . return (Τ a b)

I don't like that I need to identify and bind the variables a and b; I don't like that one bit! In my eyes, identifying these variables does nothing to make the program more declarative. I would much rather write these functions in the following manner...

> liftLoc = next >>=> next >=>> Loc
> liftPos = liftLoc >>=> liftOrient >=>> Pos

...with the my weird monadic stream operators defined (obviously) as follows...

> (>>=>) :: Monad m ⇒ m a → m b → m (a, m b)
> mA >>=> mB = mA >>= λa . return (a, mB)

> (>=>>) :: Monad m ⇒ m (a, m b) → (a → b → c) → m c
> mTup >=>> τ = mTup >>= λ(a, mB) . 
>               mB >>= λb . return (τ a b)

...but then I worry that this syntax is too esoteric for its own good. Thoughts?

Yes, a person leaving a remark pointed out that I've reinvented liftM2. Obviously so, in retrospect. I'm on a roll! After a year of entries, I suppose I'll have reinvented most of Haskell's standard library.

Actually for binary situations (that is, for types that take two arguments from the stream to construct), I think I will use these special streaming monadic operators, but when types become more complex, then more, and more complex, operators are required (each new argument for a type doubles the complexity of each new operator). This tells me (as it has already told Uustalu and Vene) that monads are not the best way to go about scanning/parsing streams to extract an internal representation of the grammar.

Scanner-parsers I: lifting functions

2008-08-28T19:25:00.000-07:00

I'll start right off with an apology: I would've loved this entry to be on comonadic parsing, but I'm still trying to get my head around the Uustalu and Vene papers — I keep looking in the papers for something that says the equivalent of "... and this comonadic parsing technique resolves to something very much like Prolog's definite clause grammar", but I didn't see this conclusion in their papers. Would somebody please point out the gap in my understanding?

Instead, we'll concentrate on converting a very simple command language into an internal representation using lifting functions. Daniel Lyon suggested this "Mars rover" problem.

> module MarsRover where

> import Char
> import Data.List

Problem statement: MARS ROVERS

A squad of robotic rovers are to be landed by NASA on a plateau on Mars. This plateau, which is curiously rectangular, must be navigated by the rovers so that their on-board cameras can get a complete view of the surrounding terrain to send back to Earth.

A rover's position and location is represented by a combination of x and y co-ordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom left corner and facing North.

In order to control a rover, NASA sends a simple string of letters. The possible letters are 'L', 'R' and 'M'. 'L' and 'R' makes the rover spin 90 degrees left or right respectively, without moving from its current spot. 'M' means move forward one grid point, and maintain the same heading.

Assume that the square directly North from (x, y) is (x, y+1).

INPUT:

The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.

The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover's position, and the second line is a series of instructions telling the rover how to explore the plateau.

The position is made up of two integers and a letter separated by spaces, corresponding to the x and y co-ordinates and the rover's orientation.

Each rover will be finished sequentially, which means that the second rover won't start to move until the first one has finished moving.

OUTPUT

The output for each rover should be its final co-ordinates and heading.

INPUT AND OUTPUT

Test Input:

5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM

Expected Output:

1 3 N 5 1 E

Problem solution

Types

This problem simply decodes into a state machine and a command interpreter, where the interpreter first lifts the input characters into their correspondingly-typed values.

The state machine, a.k.a Mars Rover, is:

> data Location = Loc Integer Integer
> data Orientation = N | E | S | W
>      deriving (Show, Enum, Read)
> data Position = Pos Location Orientation

The typed commands are:

> data Direction = L | R deriving Show
> data Command = Turn Direction | Move

... with some Show instances for sanity checks and output

> instance Show Command where
>    show (Turn dir) = show dir
>    show Move = "M"

> instance Show Location where
>    show (Loc x y) = show x ++ " " ++ show y

> instance Show Position where
>    show (Pos loc dir) = show loc ++ " " ++ show dir

Our scanner-parser for our very simple language grabs the next thing to be scanned from the input and returns updated input.

> type Scan a = String → (a, String)

Lifting functions

The lifting functions are rather simple affairs, as they convert what's in the input stream to their typed internal equivalents:

> liftOrient :: Scan Orientation
> liftOrient command = head $ reads command

> liftLoc :: Scan Location
> liftLoc command = let (x, locstr):_ = reads command
>                       (y, out):_ = reads locstr
>                   in  (Loc x y, out)

... I'm not quite getting the intent of reads: it seems to return either empty (denoting failure) or a singleton list containing the value and the continuation (that is, to be precise, the rest of the list after the first value is read). I'm not doubting its utility, but I do wonder that the list type was the return type if it behaves as a semideterimistic function (fail or singleton success) and not as a nondeterministic one (fail or multiple successes). The Maybe data type is more closely aligned with semideterministic functions; lists, nondet. So I believe that either the Either type or Maybe are a more appropriate return for reads.

At any rate, with the above two lifting functions, lifting the position of the rover (the first line in our command language) simplifies to chaining the above two lifting functions:

> liftPos :: Scan Position
> liftPos command = let (loc, rest) = liftLoc command
>                       (dir, out)  = liftOrient rest
>                   in  (Pos loc dir, out)

So, we have the scan and parse of the starting position of the rover done. We're half-way there! Now we simply need to scan then to parse the commands. But, the neat thing for us is the following: the commands are atomic (and just one character each). There's no need for the continuation scheme that we used for scanning positions above, we just need simply map the command lifting function over the line of commands (the "command line") to obtain our internal representation:

> liftCmd :: Char → Command
> liftCmd 'L' = Turn L
> liftCmd 'R' = Turn R
> liftCmd 'M' = Move

Command interpreter

What does a command do? It moves the rover or reorients the rover. What is movement? A change in Position (via a change in Location). What is reorientation? A change in Orientation. So, a Command's action (which is either to move or to turn the rover) results in a Δ (pron: "Delta") of the Position:

> type Δ a = a → a

> command :: Command → Δ Position
> command (Turn dir) (Pos loc orient)
>         = Pos loc (turn dir orient)
> command Move pos = move pos

> move :: Δ Position
> move (Pos loc dir) = Pos (dLoc dir loc) dir
>       where dLoc :: Orientation → Δ Location
>             dLoc N (Loc x y) = Loc x (y+1)
>             dLoc E (Loc x y) = Loc (x+1) y
>             dLoc W (Loc x y) = Loc (x-1) y
>             dLoc S (Loc x y) = Loc x (y-1)

> turn :: Direction → Δ Orientation
> turn dir orient
>      = toEnum $ (intVal dir + fromEnum orient) `mod` 4
>       where intVal :: Direction → Int
>             intVal L = -1
>             intVal R = 1

I suppose turn could've been modeled more realistically on radians, and would work just the same, but since the command language is so simple (turns are exactly 90^o), I can get away with using the four points of the compass as (circularly) enumerated values.

The Glue

Given all the above, the rover simply runs as follows.

Note that I ignore the grid-size command, as it appears to be superfluous to the problem definition (collision detection between rovers and out-of-the-grid bounding errors are NOT covered in the problem statement ... since they choose to ignore these issues, I will, too).

> runRovers :: String → IO ()
> runRovers commnd = let (_:commands) = lines commnd
>                    in  putStrLn $ run' commands
>    where run' [] = ""
>          run' (pos:cmds:rest)
>               = let (start, _) = liftPos pos
>                     mycmds = map liftCmd cmds
>                     stop = foldl (flip command)
>                                  start mycmds
>                 in  show stop ++ "\n" ++ run' rest

> runTestEx :: IO ()
> runTestEx = runRovers "5 5\n1 2 N\nLMLMLMLMM\n"
>                       ++ "3 3 E\nMMRMMRMRRM"

Summary

So, there you have it, folks: scanning and parsing as mapped lifting functions. That all DSLs would be that simple, but that topic is for when I cover how I reinvent the Parsec wheel ... but in the meantime, you can read the next extry the covers scanning and parsing for this problem with the State monad transformer.

Ten = 1+2+3+4

2008-08-27T11:15:00.000-07:00

Daniel Lyons on his blog, showed us how to how to arith our way to 10 in Prolog using the operations of addition, subtraction, multiplication, and division and the numbers 1, 2, 3, and 4. A straightforward logic program, which I was hoping to duplicate the feel of in Haskell. Here's my go at it.

> module Ten where

> import Control.Monad
> import Data.List
> import Smullyan

I suppose the standard way people going about enumerating the arithmetic operations is to encode it in the following way ...

> {-
>    data BinaryOp = Plus | Minus | Div | Times deriving Eq

>    op :: BinaryOp → Int → Int → Maybe Int
>    op Plus  b a = Just $ a + b
>    op Minus b a = Just $ a - b
>    op Times b a = Just $ a * b
>    op Div   b a = if b ≡ 0 ∨ a `rem` b ≠ 0 
>                   then Nothing 
>                   else Just (a `div` b)

>    instance Show BinaryOp where
>       show Plus  = "+"
>       show Minus = "-"
>       show Div   = "/"
>       show Times = "x"
> -}

... but I shied away from that approach for two reasons: first and foremost, we have a disjoint type with enumerated values, but later we are going to choose from those enumerated values from a list of all those values. It seems to me to be wastefully redundant to enumerate the values of the type in its declaration, and then be required to enumerate those values again in their use. Wastefully redundant and dangerous — the type guarantees that I will not use values outside the type, but how can I guarantee that I've used all the values of the type in the program? I'm mean, of course, besides full coverage using a dependently typed system, that is.

So instead of the above commented out code, I chose the following type definition:

> data BinaryOp = Op (Int → Int → Int) String

This type has the advantage that the arithmetic operation is embedded in the type itself, as well as showing and equality:

> instance Eq BinaryOp where
>    (Op _ a) ≡ (Op _ b) = a ≡ b

> instance Show BinaryOp where
>    show (Op _ s) = s

> op :: BinaryOp → Int → Int → Maybe Int
> op (Op f s) b a | s ≡ "/"  = if b ≡ 0 ∨ a `rem` b ≠ 0 
>                               then Nothing 
>                               else Just (a `div` b)
>                 | otherwise = Just $ f a b

I know that some of you are going to be raising your eyebrows in disbelief: I've forsaken a pure and dependable, or compile-time, way to distinguish operations with a very weak string, or runtime, representation. The former is "just the way it makes sense" for most; the latter, my "sensible" compromise, sacrificing type safety for a more declarative representation. Again, if we had dependent types, I think there would be a type-safe way to represent arithmetic operators as comparable (distinct) and showable types ... dependent types for Haskell', anyone?

Okay, now we need to write permute, because this isn't C++ or Java. *sigh* That's correct, you heard it here first: Java and C++ are way better programming languages because they have permute in their standard libraries, and Haskell does not.

> permute :: Eq a ⇒ [a] → [[a]]
> permute list@(h:t) = [x:rest | x ∈ list, 
>                                rest ∈ permute (list \\ [x])]
> permute [] = [[]]

And from that the solver simply follows: it's the permutation of the row of numbers matched with any arbitrary (ambiguous) arithmetic operation. This has the flavor of the days when I was writing code in MMSForth, push the numbers on the stack and then call the operators. Oh, JOY! (I'll stop now.)

> solver = [twiner perms [op1, op2, op3] |
>                      perms@[a,b,c,d] ∈ permute [1..4],
>                      op1 ∈ amb, op2 ∈ amb, op3 ∈ amb,
>                      ((op op1 b a >>= op op2 c >>= op op3 d)
>                            ≡ Just 10)]

> amb = [Op (+) "+", Op (*) "x", Op div "/", Op (-) "-"]

So, all we need is the display mechanic (twiner) to intersperse the arithmetic operators between the provided numbers. I had started down this path ...

> stringIt :: BinaryOp → Int → String → String
> stringIt op num acc = "(" ++ acc ++ show op ++ show num ++ ")"

> twiner :: [Int] → [BinaryOp] → String
> {- 
>    twiner args ops = doTwine args ops True ""
>       where doTwine args ops binary acc | binary =
>                    let (arg1, rest) = (head args, tail args)
>                        (arg2, done) = (head rest, tail rest)
>                    in doTwine done (tail ops) False 
>                               (stringIt (head ops) arg2 (show arg1))
>                                         | ops == [] = acc
>                                         | otherwise =
>                       doTwine (tail args) (tail ops) False
>                               (stringIt (head ops) (head args) acc)
> -}

... looking longingly at intersperse in the Data.List module (why, oh, why! can't they have intersperse take a state-function argument? Oh, because I would be the only person using it?), but, I figured, as I have already reinvented takeWhile, I had better not reinvent zipWith here:

> twiner (h:r) ops = foldl t (show h) (doTwine r)
>    where doTwine args = zipWith (c stringIt) args ops

... *ahem* dependent types would guarantee that twiner is never called with an empty list of arguments.

I'd say my Haskell version follows in the spirit of the Prolog version in that it uses nondeterminism (of the Maybe and list MonadPlus types) to select the true equations. Weighing in at 18 lines of type declarations and code (with 4 additional lines for the module declaration and the imports), it is also about the same size as the Prolog version as well.

Goodness! Typeful logic programming in Haskell, with all the functional frosting on the cake applied for free, costs no more than developing a Prolog program, and along with the type-safety, it also carries with it the flavor and the feel of logic programming in Prolog as well.

"Lucky you!"?

2008-08-26T20:08:00.000-07:00

I'm sure some of you reading this blog share my fortune in that you are getting paid to code declaratively. I also know others of you are stuck in that ghetto of churning out web-pages from JSPs or VB.NET or Oracle Forms and are wondering how to break into that fairy-tale world where you can use a sentence with the word "λ-term" in it and not have it confused with a Revenge of the Nerds reference.

Yes, Virginia, there are actually jobs/contracts out there that pay real money for you to code declaratively. In fact, if you're in the United States or Australia, then there are "lots" of these jobs, and, if you're in Europe or Asia, there are some jobs in your country or in a country near you.

So, here you are, and you're missing the key ingredients that will secure you one of these plum assignments: professional work experience in your LoCh ("Language of Choice") 'cause your stuck writing VB scripts, not (e.g.) Haskell, and phone calls from recruiters or companies wanting (e.g.) Haskell programmers 'cause you don't have (e.g.) Haskell on your resumé (because you never, ever lie on your resumé) and 'cause no recruiter nor company will ever admit they need something other than a programmer with Java or C# experience if they are hunting.

Real life story: a recruiter solicited me with no idea that I had Prolog experience for a Prolog req. because she was so used to seeking Java programmers, and all her other contracts needed Java programmers, that the thought never occurred to her. Only my "and, yeah, I also have experience in Mercury, which is like Prolog, and Dylan, which is like Lisp" woke her up to that nagging req. that she thought she was never going fill.

So, for all of you out there thinking about looking, you probably need a couple of questions answered. Like: how do you prepare for these jobs, and then, how do you find them? Well, I'm not going to give advice here on what should work, I'm going to tell you what worked for me. But since my experience may be atypical, maybe some of the readership that do have functional or logical programming jobs can chime in with your own stories that show easier routes to success.

Here's how I didn't get my paying jobs coding in Dylan and Mercury and Prolog and Haskell (yes, my current job is accepting some code in Haskell and they are building a foreign interface to Haskell in their Prolog engine. Win!):

I neither lied on nor fudged my resumé.

Some people think that reading a book on Hibernate allows them to enter a bullet on their resumé as on-the-job work experience. Those kind of antics may get one in the door, but the thing that keeps one on the payroll is "am I confident and competent building systems with this technology?" ("did I really do this?"), not "can I learn the technology I listed on my resume on the new job?" ("do I think I can do this?")

I didn't get my job from any of the companies listed on haskell.org or schemers.org or <anything>.org.

Why? Because these listings are usually from somebody who got to write a code snippet or a pet project in their favorite language under the radar and are crowing about it on their-favorite-language.org website. Sure it's wonderful that XYZ corp is using Haskell, but does the HR department know about it? No. Is is in their budget to hire a Haskell programmer? No. You don't need to believe me on this one, however. You can send an email to every single one of those companies, just like I did, and get the null-responses and the "this email address does not exist" bounces, just like I did. Knock yourself out.

I also didn't get a job or contract working for the luminous companies in the declarative world.

Don't know why here, but I can guess. It may be that Galois or Jane's Capital or Ericsson or whatever gets a few solicitations a quarter, and they are already up to their gills in talent. If they already have all the work they want in that domain, and they have already some people with some time on their hands, they aren't going to hire a new person, and give that person nothing for their job, just because that new person is so excited about the opportunity to code declaratively.

And the larger the company, the harder it is to thread one's way through the layers of bureaucracy to reach the isolated island that uses your LoCh. Sure, IBM (Tivoli) and Microsoft (Windows Registry) use Prolog, but good luck finding a person to speak about that in those empires. And since your LoCh is so niche in those empire, good luck finding an opening.

So, I guess it was pure-D-luck that I was on four contracts where I used Dylan, and one contract where I used Smalltalk, and one contract where I used Mercury, and two contracts where I used Prolog, and one contract (so far) that I'm using Haskell.

... or maybe not.

So, how did I get to use these languages that I (have) love(d) on these contracts?

First and foremost, by being the best d*mned Java or C++ programmer their management had ever seen. In 1996, I took three Java books on my honeymoon, and read them. (Yes, Virginia, 12 years later, we are still married.) Every single night after work on my C++ contracts, I would read something from Design Patterns and Stroustrup. Work assignment scoped to two months, end-to-end, I would complete in two weeks.

What did that give me? Trust, latitude, tolerance and time. Management knew they didn't need to look over my shoulder and they would allow me to do the jobs my way. It then was a very simple step from writing each web-page as its own JSP to writing a Dylan program that generated 100s of JSPs from templates. Then I would show management the Dylan program. ("This, boss, is how I've been so efficient").

Most of the time it worked ("That's awesome, Doug." "Would you be willing to be a reference for me?" "Sure."), sometimes it didn't ("How are we going to maintain this when you're gone? Rewrite it in Java." "Yes, ma'am."). Where it worked, I added it to my resumé; where it didn't, I didn't.

Next, I was the best salesman in the organization, better, even than the PR department. At socials with the customer, all the programmers would line up against the far wall ('cause programmers are shy, don't you know), except me. I would cross the room and walk right up to the customer with a ready handshake ("Larry, hi; I'm Doug Auclair, and I'm working on solving your problems"), this also applied to internal customers ("Paul, nice to meet you; I'm glad the VP of ITT is checking out this satellite program").

What did this get me? Call backs and word-of-mouth that allowed me to set the terms of the contract ("Hi, Doug, this is Bruce at Raytheon, we need somebody good on this new contract, so we called you." "Sure, Bruce, this is my rate." "That won't be a problem").

If you want what you want, you must be good where you are and you cannot be a wall-flower. People with the power to decide must think of you first because a) you've excelled in your current work and b) you've told them so.

Next, I always had my eyes and ears open and, when I was good, I opened my mouth only after someone had gotten their gripe off their chest. You know what a gripe is? To me, a gripe is a contract. "!@#$%^*, we need a phoneme-based name-matcher but the programmer who built it in assembler retired years ago!" (Trans: Doug, we need you to write a fuzzy ILP system in Mercury) "I sure wish we could use the function object templates you've written about in the C++ system I'm building." (Trans: Doug, come on board to show me how Dylan will make this a whole bunch easier.) "We want your system to extract meaning from text documents, but extracting meaning from the images is too hard; don't bother with that." (Trans: Tell us about image processing and classification with Self-Organizing Maps and Pulse Coupled Neural Networks.). Each of the above gripes led to work, that is authorization and funding, for me to write in my LoCh (Mercury, Dylan, and Haskell) that was outside the, erhm, comfort-language of providing company.

How did I have the confidence to offer those suggested courses of action and then have the competence to build them to delivery? Listening is key. Nobody listens in our industry, so when somebody does listen, the griper is so relieved that somebody cared that they weigh the response with much greater significance. That I had these novel, but workable, courses of action to offer comes from what I did in the next, final, point.

Finally, I became a teacher. Being a teacher, a real teacher, means first you are a learner and learn more than anyone you know about the topic, and second you are a doer and are better at using the technology to solve the given problems than anyone else on the team. Those two things are prerequisites to being a teacher, but they don't make you a teacher. No, to be a teacher, you must write, write, and then write some more about the topic: documentation (users manuals and programmer manuals), white papers, articles, quizzes, aphorisms. Then after the writing comes the lecturing: I spent years developing and then teaching continuing education courses at the local community college after I gave brown bag lunch lectures at my place of work. I got two of my better contracts from company owners tripping over my written materials: a Dylan project and a Prolog-based agent project.

By the way, teaching is not droning on for an hour or for four hours. Teaching is preparation, to the tune of 13 hours of prep work for each hour in front of the class (I did). Teaching is getting up on top of the desk to do flamenco (I did), teaching is jumping up and down, up and down, jackhammer-style to drill in the point (I did), teaching is having the students wonder what I was on and could they get a prescription ("Class, this is Doug without coffee!"). Teaching is inspiration; it is the flame to ignite the students' imagination.

I had something like 3,000 students under my tutelage from the brown bags and my continuing education courses (that I was paid to teach), from coders to company presidents ... do you think I have a problem with my contact network?

Oh, but that's easy for an extrovert like you, Doug! But I'm naturally shy. Dude, don't give me that line! On Myers-Briggs, I'm either INFJ or INTJ, my "I" (introversion) is so extreme that it actually blows the percentile curve. I HATE interacting with people, so much so that it takes an additional 8 hours for me to recover from a meeting or class that I run (and since I'm president of my independent consulting firm, I run all the meetings and teach all the classes), but I LOVE coding declaratively more. Once you know what you must have, you'll find a way to get it. The excuses you used to make for not getting what you must have become just that, excuses; when you have that burn, that's when you start finding ways to the desired end.

Well, unlike Java jobs or C# jobs or VB jobs, where one can scan the newspaper or go to dice.com, these magical jobs are not the ones I get when recruiters solicit me (three times a day). No, they appear between the cracks of the sky when it rends in two. All but one contract (that did come from dice.com) came from the company CEO pulling me aside or phoning me out of the blue from the materials I had published inside the company where I was employed, or from my web-sites on programming languages.

Usually and because of the exclusivity of the work it takes anywhere from at least 3 months to 2 years to secure these kinds of contracts, so the adage "Don't quit your day job" is an appropriate one here. When I do get these contracts, however, they usually last longer (3 years) than the Java/C++/XML/web-services-code-grinder ones (that usually last around 6 months), and the peer group is much more intelligent, genteel and just plain more interesting than the code-grinding crowd. Is is harder to find these magical contracts? Yes, they are rarified air. But are they worth preparing for and then finding? Definitely.

So, yes, I was lucky to work on 7 paying contracts using declarative languages, because I was the best code-grinder on my current job, I used my LoCh effectively and then wrote about the successes and taught techniques to my peers, all of which luckily attracted the notice of hungry companies needing a competitive advantage.

Luck, you see, is when preparedness meets opportunity.

Using Difference Lists

2008-08-13T22:12:00.000-07:00

I posted my enthusiasm about difference lists for Haskell earlier this month, but then became sidetracked by combinators and reading lists, so, let's get back on track.

Difference lists are a (very) useful data structure in Prolog, particularly when it comes to parsing with definite clause grammars (DCGs) and when it comes to list construction (again, using DCGs). Why? Well, to answer that question, let's examine the structure of difference lists. The Prolog (or relational) representation of a difference list is of the form:

X = [1,2,3|Y] - Y

What that relation describes is that X is the difference of the pair of lists of (first) [1,2,3] appended with the list Y minus (second) the list Y.

Well, what is the value of the list Y? To a Prologian, this question is not important (for Y, being a logic variable, can be any list or, even, not a list at all because the variable is still uninstantiated (a "free" variable)). Its importance is that it gives us an "instant" index into the list after the elements we've already processed. The significance of that index for parsing is that we now have a stream over the parsed (list) data, which gives us the ability to translate BNF grammars directly into working parsers. The significance for list construction is that we "simply" walk "backward" through the DCG to construct a list from a (parsed) internal representation, without paying the linear cost of either (a) traversing the list each time to add a new element (which results in exponential time list construction) or (b) building the list in reverse (adding new elements to the head of the list) and then applying reverse to the end result.

"Big deal!" you scoff, "zippers [also called 'finger trees'] already give us indices into data structures. Who needs a funny-looking specialized zipper just for lists?"

"Good point!" is my response. Zippers are powerful and flexible data structures that not only provide that index over any data structure, but, even better than difference list's index that only goes forward (with any dignity) in constant time, the zipper's index can go both forward and backward through that (generic) structure in constant time. So, if you are not familiar with zippers, I request that you run, don't walk, to a good overview to learn more about their utility.

With all their flexibility and power, in certain situations, a zipper is not the correct choice for some list processing tasks; the difference list's simplicity shines in these situations. First, for the unidirectional index of the difference list (it moves forward through the list well, but backwards ... not so much), this, for list construction purposes, is hardly ever an issue, and if it becomes one, then backtracking is easily installed with some MonadPlus magic. Next, you, the coder, are responsible for constructing a zipper list data type each time you need one, but Don Stewart has provided Data.DList; no construction necessary! Last, an example structure of a zipper list, for the list a++b is (reverse a,b), so if we wish to reconstruct the original list, for an a of large magnitude, we still pay the linear (reverse) cost in reconstruction as well as the linear cost of appending b to that result.

You heard it here first, folks — difference lists: [zipper lists] can't touch this!

Okay, I've finished throwing it down for now. Let's look at difference lists from the Haskell perspective and then use this data structure in a list construction example.

> import Data.DList

For my examples, I'm going to be looking at the subset of difference lists that I can compare and see:

> instance Eq a => Eq (DList a) where
>     x == y = toList x == toList y

> instance (Eq a, Show a) => Show (DList a) where
>     show x | x == empty = "\\x -> [x]"
>            | otherwise  = "\\x -> [" ++ show (head x)
>                           ++ doShow (toList (tail x)) ++ ":x]"
>         where doShow [] = ""
>               doShow (a:b) = ", " ++ show a ++ doShow b

With the above instance declarations, we see that

(singleton 1) `snoc` 2 `snoc` 3

gives us the representation

λ x . [1, 2, 3:x]

... snoc appends an element to the end of a list (so it's the reverse of cons).

Prologians are always smug with their ability to create an infinite stream of 1s with X = [1|X]. And, no doubt about it, Prolog is a programming language that makes list construction easy ... *ahem* almost as easy as list construction in Haskell ("Your list comprehensions outshine even Prolog for sure..."):

repeat 1
[1,1..]
... and now with difference lists ...
let x = unDL (singleton 1) x in x

But no self-respecting Prologian would freeze their interpreter with a such a rash proof; Haskellians have no such concern, thanks to weak head normal form:

take 5 (repeat 1)

So there!

Let's examine an application of difference lists. I have a little scanner that I use to help me in my oration. The meat of the algorithm (before difference lists) was as follows:

> lettersIn word = lettersIn' word []

> lettersIn' [] ans = reverse ans
> lettersIn' (h:t) ans | isLetter h = lettersIn' t (h:ans)
>                      | otherwise  = reverse ans

Ugh, yes, reverses galore! This is an oft-recurring pattern in Haskell code that is very easily fixed with some difference list magic:

> lettersIn word = lettersIn' word empty

> lettersIn' [] ans = toList ans
> lettersIn' (h:t) ans | isLetter h = lettersIn' t (ans `snoc` h)
>                      | otherwise  = toList ans

A very simply example, I grant you, for if we take a list whose elements are all in the set of the alphabet, the above code is a very complicated way of reinventing the id function. Or, put another way, who's going to teach me about scanl? Hm, would I be required to use the continuation Monad to escape the scan, I wonder? But you get the general idea for list construction, right? Instead of building the list by adding to the head ("cons"ing) and then applying reverse to the result, the different list allows one to "snoc" each element and return the correctly ordered result. For a single list construction, the benefit may not be all that obvious, but when one builds, e.g., an XML generator for a complex internal representation, reversing the reverse of the reversed reversed child element becomes an odious labour — difference lists eliminate all the internal juggling, replacing that complication with a straightforward constant-time list and element in-place append.

So, next time you need to do some list construction, instead of falling back on the reverse standby, flex your new difference list muscles; you'll be pleasantly surprised.

Combinatory Birds as Types

2008-08-12T11:18:00.000-07:00

This post is composed nearly entirely of the work of readers responding to my previous post that dealt with combinatory logic combinators. That post implemented the Smullyan combinatory birds as functions. This is the obvious approach, as birds and λ-terms have a very simple and straightforward (obviously bidirectional) mapping. A few readers improved and explained some of my combinators (S and W) by using the ((->) a) Monad, and I rolled those improvements into the original post, but these improvements are still in the combinators-as-functions domain.

Two readers, ryani and david, provided implementations for two combinators that I've had difficulty with. I've implemented the "void" combinator from the Unlambda programming language (or as Smullyan calls it, the "hopelessly egocentric" bird) using only the S and K combinators. Haskell is (thankfully) not so restricted, so ryani implemented that combinator as a type and then as a class. The thrust of ryani's void-as-type implementation is as follows:

> {-# LANGUAGE RankNTypes #-}
> newtype Void = V { runV :: forall a. a -> Void }
> v :: Void
> v = V (\x -> v)

Simple and sweet! And, the ranked type resolves the type-circularity ("void x is of type void"). So, for example:

> :t runV v 0
runV v 0 :: Void
> :t runV v "hello"
runV v "hello" :: Void
> :t runV (runV v 0) "hello"
runV (runV v 0) "hello" :: Void
... etc ...

In my implementation, I represented that the "void" combinator is "enough" K combinators (where "enough" was more K combinators than applications); ryani takes that exact approach using a class-based implementation:

> class Voidable r where vc :: r
> instance Voidable () where vc = ()
> instance Voidable r => Voidable (a -> r) where vc = k vc

(so void is represented as the Haskell type and datum () (pron: "unit")) e.g.:

> vc "hello" :: ()
()
> vc "hello" 123 :: ()
()
> vc "hello" 123 (Just k) :: ()
()

As ryani points out, the type-checker supplies the correct number of K combinators to match the number of function applications. Neat!

I had left a question on how to implement the U, or Turing, combinator, and david demonstrated an implementation where the class of all combinatory birds were a type (with two free implementations of good-ole factorial, to boot):

> data Bird a = B (Bird a -> Bird a) | Value a

> app :: Bird a -> Bird a -> Bird a
> app (B f) x = f x

> lift :: (a -> a) -> Bird a
> lift f = B (\(Value x) -> Value (f x))

> unlift :: Bird a -> (a -> a)
> unlift f = \x -> case (f `app` Value x) of Value y -> y

> -- Uxy = y(xxy)
> u = B (\x -> B (\y -> y `app` (x `app` x `app` y)))

> -- sage1 = UU [geophf mumbles: "Sweet!"]
> sage1 = u `app` u

> -- Yx = x(Yx)
> sage2 = B (\x -> x `app` (sage2 `app` x))

> fix f = unlift (sage1 `app` B (\g -> lift (f (unlift g))))
> fix2 f = unlift (sage2 `app` B (\g -> lift (f (unlift g))))

> facR :: (Integer -> Integer) -> Integer -> Integer
> facR f n = if n == 1 then 1 else n * f (n - 1)

> fac = fix facR
> fac2 = fix2 facR

I'm sure both ryani and david would claim that the M combinator (where m x = x x), so useful in Smullyan for implementing several birds (such as the "void" combinator), is not hard to do in Haskell given the above implementations. Do you see how to do it? Wanna race?

Getting Better, part ][

2008-08-12T11:02:00.000-07:00

A reader wrote in follow up to the previous post ("How do I get better? A reading list") and asked "Which of the three following books has the most bang for the buck?

To Mock a Mockingbird, Smullyan

Algorithms, a Functional Approach, Rabhi, LaPalme

How to Solve it, Modern Heuristics, Michalewicz/Fogel"

Not that I particularly agree that the above three are the top three of the larger book list, but I responded thusly:

The difficulty lies in the differences in our opinion as to which direction the bang makes the buck well-invested.

A facile answer, but also useless for you, I suppose, is that they all have a high bang/buck ratio, much more so than most the drivel out there. So let me explain their utility to me, and perhaps that will help you make a more informed decision as to how to proceed.

To Mock a Mockingbird, Smullyan: I absolutely consumed. But are you ever going to use combinatory logic combinators when coding? I do, and no-one else in the world does (Okay, maybe David Turner still does an occasional SK bit of low-level coding). But as an introduction to the magic of first class functions and construction through composition (that is, in other words, "Coding in the Haskell-style") there is no equals as to its lightness of touch as well as the density of concepts. You learn from this book and delight in it.

Algorithms, Rabhi & LaPalme. I carry this book incessantly, into meetings (where I am to be a passive participant), on trips, etc. Certainly it teaches one about data structures and algorithms in Haskell, using practical examples. But it also opens one's eyes to possibilities of programming. It is a powerful (but not dense), little book. It is, however, dated, especially in the light of the explosion of new ways to use more-recently developed mathematical structures (from category theory, particularly, monads, arrows, and comonads). It does not cover these recent developments, but the ones it does cover, it covers extraordinarily well.

How to Solve It, Michaelwicz & Fogel. Thick, dense, impressive. I don't think I've gotten much further than chapter 2 — this is my fault, but it is also the book's unapologetic full coverage and well as its assumption that they are not addressing 7-year-olds that make progression, for me, at least, arduous. Worth reading? Absolutely, as it addresses the fundamental problems of problem-solving (at the top of their list is that problem solving is hard, and our education has flippantly ignored that bald fact) and proposes solutions that are novel, scintillating, simple, and, once discovered, obvious. I recommend you read more than the first three chapters in a book store (prepare to spend more than a few days in this task) to see if you can justify purchasing it for continued reading.

So, did I provide accurate guidance for the inquirer? Or, where my assessments off-base? I won't disclose the choice the reader made, but I will ask instead: which book would you have selected given the above reviews?

How do I get better?

2008-08-03T18:32:00.000-07:00

I just fielded a question from a programmer who wishes to improve his (Haskell) programming skill, and I responded with a reading list (below) and a referral to the Project Euler problems site. But I also see this as an excellent question for myself. How do you, genteel reader, recommend I improve my skill as a coder? Or, put another way, what book, or books, and which article, or articles, so totally transformed you from J. Random Hacker to J. Über Hacker (hacker being coder, or mathematician, or logician, or rule developer, or ...)?

My list is as follows. Would you kindly tell me what I need to read right now so I can see the light as you have?

Books for learning:

The Art of the Metaobject Protocol, Moon, et al
To Mock a Mockingbird, Smullyan
Reasoned Schemer, Bird, et al
Algorithms, a Functional Approach, Rabhi, LaPalme
Genetic Algorithms, Goldberg
How to Solve it, Modern Heuristics, Michalewicz/Fogel
Godel, Escher, Bach, an Eternal Golden Braid, Hofstadter
Prolog Programming for AI, Bratko
(and, after a year of programming in Prolog), Craft of Prolog, O'Keefe
A Grammatical View of Logic Programming, Deransart/Maluszynski
An Introduction to Mathematical Philosophy, Russell

Books for Joy:

Testaments Betrayed, Kundera
Last Samurai, DeWitt
Lord of Light, Zelzany
American Gods, Gaiman
Complete Enchanter, de Camp
Moor's Last Sigh, Rushdie

Noosphere:

"To Dissect a Mockingbird" article, Keenan
The lambda papers, Steele/Sussman
Growing a language article, Guy Steele
AI Junkie site
sigfpe.blogspot.com blog
randomhacks.net blog
the Monad.Reader (on haskell.org)
Comonad.Reader blog
"What the Hell are Monads?" article, Winstanley
"Monad Transformers, Step by Step" article, Grabmueller
"Generalising Monads to Arrows", Hughes
"Theseus and the Zipper", on the Haskell Wiki
"Escape from Zurg: Exercise in Logic Programming", Erwig
And for language construction/deconstruction: Lazy K, Jot, Iota and Whirl (well, at least they aren't INTERCAL ...), ... I suppose brainf**k should be mentioned here too ...
"The tale of N-categories" serial, starting with week 73, Baez

Combinators in Haskell

2008-08-02T20:14:00.000-07:00

In this article, instead of continuing along my path of shoving Prolog (predicate logic) into Haskell, I'll take a break from that and shove Haskell into Haskell. This turn comes by way of my recent professional experience working with Prolog — I found myself oftentimes needing to write some purely functional code, but I found the Prolog semantics getting in my way, so, borrowing some of the ideas from my previous professional programming experiences with Mercury and Dylan (when Harlequin was still a going concern, and had picked up the Dylan ball that Apple, then CMU, dropped, making a really sweet Dylan programming environment), I implemented a set of libraries for Prolog, including basic ZF-set operations, propositional logic syntax, list/set/bag utilities, and the combinator logic of Schönfinkel.

"geophf!" You exclaim, horrified, "you don't really use combinators to write working production code, do you?"

Well, yes, and I also proposed a new one in addition to the ones covered by Smullyan in To Mock a Mockingbird, and have studied the make-up of the "void" combinator of Unlambda, so I'm one of those kinds of programmers.

In short, when I was working with Prolog, I shoe-horned a Haskell interpreter into to be able to write map and fold when I wished to write map and fold. Since Prolog has DCGs (Definite Clause Grammars), I lived a monad-free and worry-free life. Ah, yes, those were the days.

That was quite a trip down memory lane. Looking back, I marvel at my fortune, not only have I professionally programmed in those languages (and VisualWorks Smalltalk; that was fun when I presented the boss a solution in two weeks that he was expecting in two months — he was so impressed that he bought the VisualWorks system for the contract, made me mentor a junior programmer on Smalltalk (Chris Choe, a good guy to work with), and had me teach a brown bag course at work on Smalltalk, but I digress, again), but it looks like Haskell is now part of our solution at my current place of work.

Life is good.

Of course, it would be so much better if I had access to the primitive combinators in Haskell (did Miranda allow that kind of low-level access, I wonder). I mean, why should one write out 'const', a whole FIVE characters, when one simply wishes to use the K combinator. I felt that very pain all too recently. I had that freedom using my combinator library when I was working on Prolog ... goodness, even MITRE fabricated the Curry Chip.

So, I could not put it off any longer, I pulled out my dog-eared copy of Mockingbird and wrote the CL module, as I didn't see one in the Haskell standard library. It went surprisingly quickly and easily. There were a few snags, Prolog, being dynamically-typed, allowed me to define the reoccuring combinators of L, M, and U (definitions of the combinators are available in my combinator library or tabled form or as graphical notation (which includes a very nice write up of propositional logic in CL)), but Haskell's type system complains of an occur-check error. I have the hack to define the Y combinator ...

fix f = let x = f x in x

... but I'm having difficulty hacking the other self-applying combinators; any suggestions on how to implement those? I'm particularly interested in implementing Turings' universal combinator ...

Uxy = y(xxy)

... because of its interesting properties I'd like to explore.

Anyway, here's the ones I do have.

> module Smullyan where

It was pointed out to me in the comments that if you make the ((->) a) type a Monad, then some of the combinators simplify to monadic operators.

> import Monad
> import Control.Monad.Instances

These are some of the combinators presented in Smullyan's To Mock a Mockingbird. Some have direct Haskell equivalents, e.g.: I ≡ id, K ≡ const, C ≡ flip, B ≡ (.), but then that just makes my job easier here. I also admit a preference to the Schönfinkel combinators over the renamed Haskell equivalents, so here is the library.

We will not be defining combinators here that cause an occurs-check of the type system, e.g. L, M, U, but we can define some interesting ones, such as O and Y by using work-arounds.

If we wish to start with λ_I, then its basis is formed from the J and I combinators.

> -- identity (I have no idea to which species belongs the 'identity' bird)
> i :: a -> a
> i = id

> -- jay: jabcd = ab(adc)
> j :: (a -> b -> b) -> a -> b -> a -> b
> j a b c d = a b (a d c)

I actually spent quite a stretch of time building the other combinators from the JI-basis, e.g., the T combinator is JII, the Q₁ combinator is JI, etc. When I attempted to define the K combinator, I ran into a brick wall for some time, until I reread the section in Mockingbird about how the noble basis has no way to define that abhorred combinator. Since that time I've fallen from grace and have used λ_K, but I've always wondered since if a complete logic could be reasonably expressed in λ_I, and if so, how would that logic be implemented? I haven't come across any papers that address these questions.

Musing again, let's define the basis of λ_K which is founded on the S and K combinators.

> -- starling: sfgx = fx(gx)
> s :: Monad m ⇒ m (a → b) → m a → m b
> s = ap

> -- kestrel: kab = a
> k :: a -> b -> a
> k = const

... okay, that wasn't too hard, so, SKK should be I, right?

--- :t (s k k) :: a -> a ... oh, yeah!

let's continue with some of the other combinators:

> -- bluebird: bfgx = f(gx)
> b :: (b -> c) -> (a -> b) -> a -> c
> b = (.)

> -- cardinal: cfgx = gfx
> c :: (a -> b -> c) -> b -> a -> c
> c = flip

Now we start defining combinators in terms of simpler combinators. Although, we could have started doing that once we've defined S and K, as all other combinators can be derived from those two.

> -- dove: dfghx = fg(hx)
> d :: (d -> b -> c) -> d -> (a -> b) -> a -> c
> d = b b

> -- thrush: txf = fx
> t :: a -> (a -> b) -> b
> t = c i

> -- vireo (pairing/list): vabf = fab
> -- e.g. v 1 [2] (:) -> [1,2]
> v :: a -> b -> (a -> b -> b) -> b
> v = b c t

> -- robin: rxfy = fyx
> r :: a -> (b -> a -> c) -> b -> c
> r = b b t

> -- owl: ofg = g(fg)
> o :: ((a -> b) -> a) -> (a -> b) -> b
> o = s i

> -- queer: qfgx = g(fx)
> q :: (a -> b) -> (b -> c) -> a -> c
> q = c b

-- mockingbird: mf = ff
m = s i i

... ah, well, it was worth a try ...

> -- warbler: wfx = fxx
> w :: Monad m ⇒ m (m a) → m a
> w = join

> -- eagle: eabcde = ab(cde)
> e :: (a -> b -> c) -> a -> (d -> e -> b) -> d -> e -> c
> e = b (b b b)

With the above definitions, we can now type-check that my JI-basis is correct: the type of I already checks, and the type of J should be equivalent to B(BC)(W(BCE))), ...

:t (b (b c) (w (b c e)))
(b (b c) (w (b c e))) :: (d -> e -> e) -> d -> e -> d -> e

and it is ... yay!

-- lark (ascending): lfg = f(gg)
l = ((s ((s (k s)) k)) (k (s i i)))

l :: (a -> b) -> (c -> a) -> b
a b = a (b b)

... ah, well, another one bites the dust ...

but we can define Y, albeit with a let-trick, thanks to Dirk Thierbach, responding to the thread "State Monad Style" on comp.lang.haskell:

> fix :: (a -> a) -> a
> fix f = let x = f x in x

> -- sage/why: yf = f(yf)
> y :: (a -> a) -> a
> y = fix

So, there you go, 15 combinators to get you started; now you can program a functionally pure and mathematically sound version of Unlambda (which exists and is called Lazy-K, by the way) using your very own Haskell system.

After all, why should someone ever be forced to write \x -> x^2 when they have the option, and privilege, to write w (*) instead?

Apologies for late Spring cleaning

2008-08-02T16:33:00.000-07:00

It was pointed out to me that the colour cyan is difficult to read against a white background; my syntax highlighter outputs Haskell keywords as cyan, so I understand that reading the code here can be bothersome. So, I'm in the process of converting the cyan to a darker colour (which first involved me converting every <font color='cyan'> to <font color='#00c8c8'>, but then, part way through that process, I moved all font metadata to the stylesheet and now simply mark code, keywords and data types with appropriate metadata tags).

A bit of a long-winded apology for what you may see as several (and repeated) repostings from this blog.

Legal Disclaimer

2008-08-02T09:34:00.000-07:00

Parties:

"I", "me", "my", "mine", the author, geophf, aka Douglas M. Auclair
"You", "your", the reader, user, coder, redistributor, referencer. Some non-exhaustive examples of "You" include, J. Random Coder, J. Random Corporation, J. Random Defense Agency, J. Random Financial Institute, J. Random Blog, J. Random for-profit corporation/LLC, J. Random Sovereignty, or http://planet.haskell.org ... just as examples.
"This blog", http://logicaltypes.blogspot.com, its content and entries originating from me.

License:

The words of this blog, http://logicaltypes.blogspot.com, are freely available to be read, to be commented on, to be referenced, or to be copied. I, the author, would like attribution, either to this site (an URL as reference is appropriate) or to the author, geophf, aka Douglas M. Auclair, but do not require it. I would also like to know if you find the topics discussed here useful, by either leaving a comment on this blog in the standard fashion, or by sending me an email at the scrambled email address of doug.at.cotilliongroup.dot.com. Descramble in the standard way.

The code in this blog is also free and freely available for commercial, noncommercial, academic or non-academic (if you happen to be a maraudering visigoth coder) use. Attribute is requested as above, but not required. Notification, as above, is also requested, but not required.

Limitation of Liability:

Note that, although the code and words are free and freely available for use and redistribute, no guarantee is made for any word or code sample published here. Some non-comprehensive examples include the following: if you use this code in a missile guidance system, and that missile falls in a populated area of friendly forces and civilians, I, my words, and my code are not to be held responsible for the resulting damage to life and to property. Or, if you implement systems published in this blog in a clustered system, and that system becomes self-aware, like Cyberdyne or the Matrix, and decides either to wipe humanity off the face of the Earth by triggering an all-out global thermonuclear war or by constructing power plants composed of the now-enslaved human population, I, my words and my code are not to be held responsible for the loss of life, freedom or property. Or, if you use this code or the ideas explored here in a Mars rover, and it offends the space alien natives, and the descend in force, 'War of the Worlds'-style, I, my words, and my code are not to be held responsible for the resulting loss of life and damage to property. Or, if you implement this system in a new Qbit supercomputer, and it results in either a singularly, sucking up the world Donnie Darko-style, or it results in a readjustment of space-type causing a complete quantum collapse of the universe, then I, my words, and my code are not to be held responsible for the early onset of the rapture. The examples enumerated above serve only to illustrate that I, my words and my code may be used but any and all damage resulting from such use, no matter how small or how catastrophic, may not be held responsible for that damage, legally, financially, or otherwise.

Exemption from obligation:

Conversely, should you use this code, or the words of this blog, and the use results in making, earning or saving money, property or life, such as, non-exhaustively, making profit in the stock market, or gaining a strategic or tactical advantage on the battlefield, or locating 3 missing teenagers, or saving 150 sailor's lives at sea, or seizing 26 million USD-worth of illegal narcotics per month, you are under no obligation to recompense me for profits or property gained or seized, lives saved, or other benefits merited. If possible and desired, I would like attribution in the code or words used and notification of the positive result of said use, but I also understand whims of corporate and personal desires as well as restrictions of non-disclosure agreements and concerns of national/world security, so attribution and notification are desired, as above, but not required. The examples above illustrating exemption from your obligation are neither exhaustive, meaning any gain is covered in this exemption clause, nor are they meant to illustrate implied or real events that have occurred in the past, present or future: I make no claim as the efficacy of me, my words, or my code in any of the above illustrations, nor do I make a claim that the above illustrations are based on any past, present or future events that may or may not have occurred.

Of course, I will not be uncivil, either. And gratuities are gratefully accepted (but, as per above, neither required nor expected). If, in gratitude, you do wish to recompense me for beneficial use of my words or code, please contact me at (scrambled) doug.at.cotilliongroup.dot.com to discuss methods of renumeration.

Coverage:

This license is put into effect for all entries posted by me. All comments by me are also covered by this license. Comments published by others are at the risk of the originators: I bear no risk nor liability of words published by others on this blog. This license is put into effect immediately, August 2, 2008, and covers all entries from the first entry ("Trivial Monad solutions" dated May 14, 2008) to all entries and content following it until such time that it may be superseded by a new license from me.

Difference Lists in Haskell!

2008-08-01T09:25:00.000-07:00

Oooh! Scrumptious!

I've discovered while exploring one of my Tangents, the Comonad.Reader, that a member of the Galois team, Don Stewart, has developed a Difference List library ... in Haskell. My initial scan of the library is that it is simple, elegant and practical. Three feathers in his cap!

Excuse me while, initially, I replace in my code the 'cons then reverse' list-building pattern with Don's DList. I also can't wait to find other applications for this type.

While I'm away doing that, you can read sigfpe's blog, particularly his clever implementation of the Fibonacci series as a comonad.

Don't know; don't care: Whatever

2008-07-31T19:45:00.000-07:00

The Maybe Monad type (covered in this blog in May) is a practical data type in Haskell and is used extensively. Since it is also a MonadPlus type, it is also immediately useful for logic programming, particularly of the semideterministic variety. Personal, I view Maybe as a second-order Boolean type, which, in itself, is a very powerful mode of expression, as George Boole demonstrated. Do yourself a favor, reread his works on algebra, or perhaps some musings from others, such as Dijkstra. Just as Donald Knuth showed that any n-tree could be transformed into an equivalent binary tree, and Paul Tarau put that to good, ahem, clause and effect, the Boolean algebra can model many other forms of algebras ... and does, for, after all, last I checked all my calculations are reduced to boolean representations (some call them binary digits).

Yes, Maybe's all well and good (and for the most part, it is — it's very well-suited to describe a large class of problems). But, as a dyed-in-the-wool logic programmer, Haskell has a bit of a nagging problem capturing the concept of logic variables ... that is, a thing that either may be grounded to a particular value (which Maybe already has when the instance is Just x) or may be free (which Maybe does not have). In short, the problem is with Nothing. And what is the problem? Values resolving to Nothing in a monadic computation, because they represent mzero, or failure, propagate throughout the entire (possibly chained) computation, forcing it to abort. Now, under the Maybe protocol, this is the desired result, but, when doing logic programming, it is often desirable to proceed with the computation until the value is grounded.

Now, deferred computation in Haskell is not a novel concept. In fact, there are several approaches to deferred, or nondeterministic, assignment, including my own unification recipe as well as the credit card transformation (which the author immediately disavows). The problem with these approaches is that they require resolution within that expression. What we need is a data type that captures succinctly this decided or undecided state. This we do with the Whatever data type:

data Whatever x = Only x | Anything

Just like Mabye, Whatever can be monadic:

instance Functor Whatever where
    fmap f (Only x) = Only (f x)
    fmap f Anything = Anything

instance Monad Whatever where
    return x = Only x
    Only x >>= f = f x
    Anything >>= f = Anything

You'll note that the monadic definition of Whatever is the same as Maybe, with the exception that Maybe defines fail on Nothing, whereas Whatever has no such semantics.

Even though Whatever is monadic, the interesting properties of this data type come to the fore in its more ordinary usage ...

instance Eq x ⇒ Eq (Whatever x) where
    Only x ≡ Only y = x ≡ y
    Anything ≡ _    = True
    _ ≡ Anything    = True

... and with that definition, simple logic puzzles, such as the following, can be constructed:

In a certain bank the positions of cashier, manager, and teller are held by Brown, Jones and Smith, though not necessarily respectively.

The teller, who was an only child, earns the least.
Smith, who married Brown's sister, earns more than the manager.

What position does each man fill?¹

An easy enough puzzle solution to construct in Prolog, I suppose, and now given the Whatever data type, easy enough in Haskell, too! Starting from the universe of pairs that contain the solution ...

data Man = Smith | Jones | Brown deriving (Eq, Show)
data Position = Cashier | Manager | Teller deriving (Eq, Show)
type Sibling = Bool
type Ans = (Position, Man)

universe :: [Ans]
universe = [(pos, man) | pos ← [Cashier, Manager, Teller],
                         man ← [Smith, Jones, Brown]]

... we restrict that universe under the constraint of the first rule ("The teller, who was an only child...") by applying "only child"ness to both the Teller and to the Man holding that Position (as obtained from the fact: "... Brown's sister ..."), but, importantly, abstaining from defining a sibling restriction on the other Positions ...

-- first rule definition: The teller must be an only child
sibling :: Position → Whatever Sibling
sibling Teller = Only False
sibling _      = Anything

-- fact: Brown has a sibling
hasSibling :: Man → Whatever Sibling
hasSibling Brown  = Only True
hasSibling _      = Anything

-- seed: the universe constrained by the sibling relation
seed :: [Ans]
seed = filter (λ(pos, man).sibling pos ≡ hasSibling man) universe

And, given that, we need define the rest of the rules. The first implied rule, that each Position is occupied by a different Man is straightforward when implemented by the choose monadic operator defined elsewhere, the other rule concerns the pecking order when it comes to earnings: "The teller ... earns the least" (earnings rule 1) and "Smith, ..., earns more than the manager." (earnings rule 2). This "earnings" predicate we implement monadically, to fit in the domain of choose ...

-- the earnings predicate, a suped-up guard
makesLessThan :: Ans → Ans → StateT [Ans] [] ()

-- earning rule 1: the teller makes less than the others
(Teller, _) `makesLessThan` _ = StateT $ λans. [((), ans)]
_ `makesLessThan` (Teller, _) = StateT $ λ_. []

-- and the general ordering of earnings, allowed as long as it's
-- different people and positions
(pos1, man1) `makesLessThan` (pos2, man2) = StateT $ λans.
        if pos1 ≡ pos2 ∨ man1 ≡ man2 then  []
        else [((), ans)]

... we then complete the earnings predicate in the solution definition:

rules :: StateT [Ans] [] [Ans]
rules = do teller@(Teller, man1) ← choose
           mgr@(Manager, man2) ← choose
           guard $ man1 ≠ man2
           cashier@(Cashier, man3) ← choose
           guard (man1 ≠ man3 ∧ man2 ≠ man3)

           -- we've extracted an unique person for each position,
           -- now we define earnings rule 2: 
           --      "Smith makes more than the manager"
           -- using my good-enough unification² to find Smith

           let k = const³
           let smith = (second $ k Smith)∈[teller,mgr,cashier]
           mgr `makesLessThan` smith
           return [teller, mgr, cashier]

... and then to obtain the solution, we simply evaluate the rules over the seed:

evalStateT rules seed

The pivotal rôle that the Whatever data type is in the sibling relation (defined by the involuted darts sibling and hasSibling). We can abduce the derived fact that Brown is not an only child, which, with this fact reduces the universe, removing the possibility that Brown may be a Teller ...

universe \\ seed ≡ [(Teller,Brown)]

... but what about the other participants? For Jones, when we are doing the sibling/hasSibling involution, we don't know his familial status (we eventually follow a chain of reasoning that leads us to the knowledge that he is an only child) and, at that point in the reasoning we don't care. For Smith, we never have enough information derived from the problem to determine if he has siblings, and here again, we don't care. That is the power that the Whatever data type gives us,⁴ we may not have enough information reachable from the expression to compute the exact value in question, but we may proceed with the computation anyway. Unlike Maybe's resolution to one of the members of a type (Just x) or to no solution (Nothing), the Whatever data type allows the resolution (Only x), but it also allows the value to remain unresolved within the type constraint (Anything).⁵ So, I present to you, for your logic problem-solving pleasure, the Whatever data type.

Endnotes

¹	Problem 1 from 101 Puzzles in Thought and Logic, by C. R. Wylie, Jr. Dover Publications, Inc. New York, NY, 1957.
²	`f ∈ list = head [x\|x ← list, f x ≡ x]` When `x` is atomic, of course `f ≡ id`, but when `x` is a compound term, then there are many definitions for `f` for each data type of `x` that satisfy the equality `f x ≡ x` and that do not equate to `id`. We see one such example in the code above.
³	I really must define a library of combinators for Haskell, à la Smullyan's To Mock a Mockingbird, as I've done for Prolog.
⁴	This semantic is syntactically implement in Prolog as anonymous logic variables.
⁵	I find it ironic that `Maybe` says everything about the resolution of a value, but `Whatever` allows you to say `Nothing` about that value's resolution.

My Top-"10" Movie List

2008-07-24T13:27:00.000-07:00

The following article is presented as a literate (literal) Haskell program. You can read it, and you can just as easily feed it to a Haskell interpreter, such as ghci or hugs.

I often get into conversations with acquaintances about movies, and when a (really) good movie is mentioned, I exclaim, "That's on my Top '10' list!", because, well, it is. After about 17 of these exclamations in a (series of) conversations, I'm often called on my assertions: "Well, what are your top 10 favorite movies then?" So, I've been forced to show my hand. Which language, though, to display this (ever-changing) list? HTML, no? XML? No, dreck, and no-no-no (been there, done that; barely survived to tell the tale). Haskell, of course. What follows is my top "10" movies as a program as activated data. If you need to see the movies in something other than code, I've posted the run result: voilà.

> module Movies where

The philosophy of this system, other than the fact that I count to 10 accurately, but I appear to have difficulty stopping there (just as the protagonist (?) in the movie "High Fidelity" has in counting to 5), is that I use the State monad to control how the output of the database is formatted. The resulting movie database is a tabled-HTML output.

Quite simply, the State monad contains a (modular) counter, and when my logic determines, then things happen at each cycle.

The Reader transformer monad carries the constant of when I wish to do these things, so the net result is a State monad counter wrapped in a Reader (constant) transformer. This article is not about the (very useful) topic of monad transformers, so I recommend the excellent article that covers that material.

> import Control.Monad.State
> import Control.Monad.Reader

> data Cat a = Cat String [a]

... unfortunately, the type-class system balks at using bare or aliased types, such as string, so here I wrap String in the "S" data type and provide my HTML representation against that.

> type Caddy = Cat (S Int)   -- quite the cad, indeed!

> data S s = S s String 

> instance Show (S s) where 
>     show (S s str) = cdata str []

Not particularly happy with the cdata transformation, either, but it's a quick and dirty implementation to handle a problem of character data in the database that would muck up an HTML representation.

> cdata [] ans = reverse ans 
> cdata (a:b) ans = cdata b ((if a == '&' then 'n' else a) : ans)

The typeclass Html is a pretty printer that generates HTML from the data set.

> class Html a where
>    asHtml :: a → ReaderT Int (State Int) String

Here, when the typeclass is given an instance of "String" (wrapped in the S data type), it pretty prints columns, wrapping every n columns were n is the constant held by the ReaderT transformer monad.

> instance Html (S s) where
>    asHtml x = do pre ← prefix
>                  post ← postfix
>                  return (pre ++ "<td>" ++ show x
>                          ++ "</td>" ++ post)
>         where prefix = do idx ← get
>                           return (if idx == 0 then "<tr>" else "")
>               postfix = do sz ← ask
>                            idx ← get
>                            put ((idx + 1) `mod` sz)
>                            return (if idx + 1 == sz 
>                                    then "</tr>\n" else "")

This is the engine control of the pretty printer. When given a category, it prints the title, resets the counter to zero, and then hands off the printing of columns to either itself (if the category (e.g. "Top 10 movies") contains categories (such as the genres)) or to the "String" printer (if the category just contains the movie list).

> instance Html a => Html (Cat a) where
>    asHtml (Cat title list) 
>          = do rows ← ask
>               put 0
>               cells ← mapM asHtml list
>               rest ← get
>               return ("\n<tr><th colspan='"
>                       ++ show rows ++ "'>" ++ title
>                       ++ "</th></tr>\n" ++ foldl (++) "" cells
>                       ++ closeCells ((rows - rest) `mod` rows))
>           where closeCells 0 = ""
>                 closeCells x = foldl 
>                                (λx y → x ++ "<td>&nbsp;</td>")
>                                "" [1..x]
>                                ++ "</tr>\n"

The database of movies follows:

> scifi, documentary, ferrn, romcom :: Caddy
> western, musicals, comedy :: Caddy
> horror, brit, oldies, sitcom, indie, drama :: Caddy

> movies :: Cat Caddy
> movies = Cat "My Top 10 Movies" 
>               [scifi, ferrn, romcom, musicals, 
>                comedy, indie, documentary,
>                horror, brit, sitcom, drama, oldies,
>                western, anime]

> anime = Cat "Animation" 
>             (map (S 1) ["Emporer's New Groove", "Wallace & Gromit", 
>                         "Shrek"])
> scifi = Cat "Science Fiction" 
>             (map (S 2) ["Solaris", "Blade Runner", "Galaxy Quest",
>                         "Donnie Darko", "Fight Club"])
> ferrn = Cat "Foreign"
>             (map (S 3) ["Le Placard", "Yojimbo", "Bleu, Blanc, Rouge", 
>                         "Siti no Samurai", "Sanjuro", "Eiron Shimbum", 
>                         "Schultze gets the Blues", "Eat Drink Man Woman", 
>                         "Legend of Drunken Master", "Shaolin Soccer", 
>                         "Kung Fu (Hustle)", "Cronos"])
> romcom = Cat "Romantic Comedy" 
>              (map (S 4) ["George of the Jungle", "Charade", "Bull Durham",
>                          "Bride and Prejudice", "L.A. Story",
>                          "Moonstruck", "My Big, Fat Greek Wedding", 
>                          "Bullets Over Broadway", "Clueless", "Ocean's 11",
>                          "Whole Nine Yards", "Princess Bride"])
> musicals = Cat "Musical"
>                (map (S 5) ["Guys and Dolls", "Singin' in the Rain", 
>                            "Mary Poppins"])
> brit = Cat "Brit"
>            (map (S 6) ["Cold Comfort Farm", "Importance of Being Earnest",
>                        "Hot Fuzz"])
> oldies = Cat "Ole Timey"
>              (map (S 7) ["O Brother, Where art Thou?",
>                          "To Have and Have Not", "Hopscotch"])
> western = Cat "Western" 
>               (map (S 8) ["Shanghai Noon", "Pale Rider",
>                           "Dances with Wolves"])
> comedy = Cat "Comedy" 
>              (map (S 9) ["Blazing Saddles", "Arsenic and Old Lace",
>                          "Dodgeball", "Young Frankenstein",
>                          "Harold & Kumar go to White Castle",
>                          "Revenge of the Pink Panther"])
> sitcom = Cat "Sitcom"
>              (map (S 10) ["Addams Family", "Addams Family Values", 
>                           "State and Main", "Rushmore"])
> horror = Cat "Horror/Suspense" 
>              (map (S 11) ["Jacob's Ladder", "Silence of the Lambs",
>                           "Shawn of the Dead"])
> drama = Cat "Drama" 
>             (map (S 12) ["Grave of the Fireflies", "Village", "Payback",
>                          "Shadowlands", "Station Agent", "Pleasantville",
>                          "Shoot 'em up", "Searching for Bobby Fischer"])
> indie = Cat "Indies" 
>             (map (S 13) ["Bagdad Cafe", "Ghost World", 
>                          "Living in Oblivion", "My New Gun"])
> documentary = Cat "Documentaries" 
>                   (map (S 14) ["Good Night and Good Luck",
>                                "thirty two short films about Glenn Gould",
>                                "Koyaanisqatsi", "Unzipped", "Ed Wood"])

This function calls the monadic system to print the movie database.

> showMovies :: Int → String
> showMovies cols = "<table>\n"
>                   ++ evalState (runReaderT (asHtml movies) cols) 0
>                   ++ "\n</table>\n"

> test = putStrLn (showMovies 3)

You can download it and see the embedded HTML in a code browser, such as eclipse. At any rate, executing test will get the above movie database in a tabled-HTML form.

What's the payoff?

Ah, yes. Well, if I had encoded my movie list in one of the currently popular metadata formats, such as HTML or XML/XSTL, then changing the number of columns per row would be prohibitively difficult with the former (HTML), and getting the metadata output as a properly formatted set of table rows would have been prohibitively difficult with the latter (XSTL). The Haskell program demonstrates both: you've seen how (relatively) easy it is to output the structured data as table rows of three columns per row, to change the number of columns (e.g.: to two columns per row), it's as simple as rewriting the test function to ...

test = putStrLn (showMovies 2)

... paid off; or, if you prefer, Q.E.D.

Alternative Implementations

Using the Reader monad is one of the ways to pass around "global" values, defining a ("global") constant function is another, sigfpe discusses those, as well as using the Reader Comonad, in an article on comonadic plumbing. I chose the Reader transformer monad instead of the Reader comonad for this article, because combining a comonad with a monad introduces arrows as the glue. Another article will explore comonads first before we dive into the thick of monad/comonad/arrow plumbing.

A Haskell Rule Engine

2008-06-04T17:35:00.000-07:00

Those of you who have read other entries on this blog know that the title does not contain a (semantic) typo. Those of you new to this discourse may wonder, "Rule Engine? Not Haskell; Prolog! End of discussion, right?"

Well, yes and no.¹

Prolog is nearly perfectly situated, semantically, for building rule engines. In fact, the Prolog interpreter is a rule engine, so making one's own rule engine amounts simply to adding rules (as rules are native-language constructs in Prolog) to the interpreter (which are then compiled into the Prolog system). What could be simpler? Well, nearly nothing, and that's why Prolog is the language of choice for these kinds of systems (and for knowledge bases, and for work-flow analysis, and for resource scheduling systems, and for ... etc).

The problem, however, is the Prolog offers a little too little and a little too much -- a little too little in typing and a little too much side-effects (à la assert, retract, and the ! (pron: "red cut")) -- and this abundance (of side effects) and dearth (of typing) both seriously hamper confidence in the correctness, or provability, of the rule system.

Let's take a moment to consider how a rule-based system works. The system is fed data; it then forms a supposition from those data, and the rules contribute, to a greater or lesser extent, to proving or disproving that supposition. Rule-based systems often, but not always, have a dynamic element to them -- rules may be added or removed (or activated or passivated) while the system is running to deal with emergent situations. Furthermore, rule-based systems often have a collaborative element to them: it is often desirable that rule-findings (or their antithesis) affect other rules in the same or similar category. Contribution, dynamism, and collaboration: these are the ingredients for successful rule-based systems. For these ingredients to work with any success, however, the supposition must have a well-understood structure as it is tested from rule to rule. Furthermore, findings that contribute to the strength of the supposition must be adjoined in well-defined ways.

Caveat: if you're looking for objectivity, read Ayn Rand. However, even though the next section is anything but even-tempered, it is indeed tempered by years of experience on real systems really in production. YMMV

The Prolog programmer writing the rule-based system may render the structure of the supposition either implicitly (by testing the dynamic structure of the supposition in the goals of each rule) or explicitly (by pattern matching in the head of each rule with tagged terms of the supposition). Either approach requires uniformity, which is just a euphemism for typing. In short, the Prolog programmer must type the supposition, but the Prolog system has no built-in check guaranteeing correctness of that type from rule to rule. This places the burden of typing on the Prolog programmer, and this often results in the programmer accidentally building an ad hoc type system extension, and often poorly enforcing that discipline from rule to rule. The result: an ill-typed supposition is allowed to pass through the rule engine generating false positives or failing to recognize real positives from the base data set.

So much for the need-for-typing screed.

Now, as for the side-effecting (a.k.a. "extra-logical") constructs in Prolog (assert, retract, and !), the literature is resplendent with caveats, so I will leave that discussion for your discovery (which would simply be to read the latter part of chapter 1 of any introductory Prolog text). I will add one bit of personal professional experience: a rule-based system built on the foundation of these extra-logical constructs (each rule issued more than a few asserts which then their duals later retracted [fingers crossed]). What happened when an unusual finding surfaced? Well, what didn't happen was a felicity in the debugger, even with a complete trace it was well nigh impossible to sort out which lemmas were asserted and at what points. Were there detritus lemmas from the previous transaction that were never retracted due to a ! or an unexpected failure resulting in backtracking? These questions were hard enough to answer in that system, but the difficulty was often compounded by the inconsistency between different findings on the exact same input data. In short, if you are a Prolog programmer who uses the extra-logical features of the language to build your rule-based system, you may have something that works from time to time, but you've also sacrificed consistency and confidence in the results. Please, for my sake,² find a way to code the system relying on the logical features of the language as the mainstay.³

We now return to our regularly-scheduled programming...

Haskell, being a typed and pure functional programming language, has its own strengths and weaknesses.⁴ The type system requires the program to be well-typed and consistent ("proofs-as-types"), otherwise the program is rejected by the Haskell system. Conversely, foundational operations of logical programming are not to be found as part of Haskell's base syntax nor semantics. Unification? Backtracking? Neither are available in "plain" Haskell. In Prolog, what are the operators for unification and backtracking? There are none, as these concepts are fundamental parts of Prolog's semantics -- they are as invisible and as necessary as the air, permeating the entire system down to every goal in each rule clause.

If not addressed, these deficiencies of plain Haskell would stop the show. However, previous articles have demonstrated typed, concise, and natural representations of choice (backtracking). So, the rest of this article will develop a rule-based system using those tools, and along the way demonstrate how "good-enough" unification may be achieved with monads in Haskell.

Before diving in to building a rule-based system in Haskell, let's pause again to consider how rule findings should be captured. Some systems are implemented where rules return a score, and the summation of all the rule findings determine if the supposition holds. Many such systems exist using this approach. The problem with this approach is that it makes defining the special cases (which always crop up in these kinds of systems) difficult. For example, a special rule finding would be: "whenever these preconditions are met, then the supposition is true, no matter what other findings occur." How does one encode this in a points-based system? "Obviously, that rule finding is alloted enough points to tip the scales in support of the supposition," you answer. However, this answer, although it works today, will no longer work as, inevitably, new rules are added (and old rules removed). When this change occurs, new thresholds are set, and the value assigned to this "ultimate" rule finding no longer triggers the expected result. Of course, one can use indirection, where the rule finding's point value is a reference to the threshold's value, but then this introduces additional housekeeping that the "simplification" of "rule findings are points" was supposed to avoid. These factors -- the paradigm broken (a rule finding is not a point result but a reference to one) and the additional housekeeping -- are an open invitation to introduce logic errors into the system during the maintenance phase of the system's life cycle.

And, what about the rule findings that monitor the users of the rule-based system? An integral part of every rule-based system (or expert assistance system) is the monitoring of the experts using the system. And, in every one of these kinds of systems, there are one or more experts who consistently subvert the system and there are certain experts who consistently and markedly outperform the system. For example, in the banking industry, the system may make recommendations that the current customer move funds over $10,000.00 out of the savings account into longer term investments, but it may also observe that the current teller is consistently successful in upselling certain profitable instruments successfully (and therefore recommend awards, promotions, or raises for that teller or may recommend pulling that teller in for interviews to enhance the system with their experience and know-how). On the other side, there may be tellers who consistently report totals that are different than what the daily transaction report shows, and so the system may recommend to managers to bring additional supervision, training, or legal action against that teller.

This subversion or excellence may be unconscious, but whatever the motive, it is imperative that this expert not be notified that their activities are being monitored. Such a rule finding ("expert in dereliction" or "expert outperforming") would, in a point-based system, result in adding 0 points, as it doesn't affect the supposition, but it does have importance elsewhere.

In short, a point-based system may work for the "normal" rules, but is unsatisfactory for any real-world system that must include special cases, such as ultimatums and rules that deal with issues not concerning proof of the supposition.

Well, if points are not the way to go, what about having the rule findings immediately trigger the appropriate action? I don't know what to call that kind of application, but it certainly isn't a rule-based system. A system such as this immediately disintegrates into incoherency. Let's examine an example to demonstrate, e.g.: a rule-based system for surveying banking customers has a rule that runs as follows: "A male, usually wearing a red shirt, and waving a pistol is a robber; call the police." So, under a ruling precipitates action system, the next person (male or female) who walks in wearing a red shirt (one of the triggers) would have the SWAT team come barrelling in, weapons free. This may impact customer satisfaction and disrupt business operations.

No, part of the raison d'être of rule-based system is that first a case must be build for, or against, a supposition with findings that are either sufficient or overwhelming in number, then, only after a compelling case is built does the system render a decision or recommendation with associated actions. The product of such systems is not only a recommendation, but also a coherent model, a "why", in support of that recommendation.

Okay, rules-as-points are out, and the imperative model ("ready-fire-aim!") is out, so what is left? The coherent model; and a very simple model is just the set of rule findings, themselves. With those findings, the arbiter subsystem may use any method for reaching a recommendation (points or winner-take-all or dispatch or monte carlo, etc), or even change its methodology, but the rule finding process does not need to change with each change of the arbiter.

Sometimes, loose coupling is good.

What better way to represent rule findings than as terms of a type? We use this representation in our example rule-based system that follows (which is the poker hand classifier developed earlier). We already have the rules for straights, flushes, straight flushes and royal flushes:

type Query = [Card] → [(Rank,Int)] → Maybe Type

royalFlush :: Query
royalFlush hand x = straightFlush hand x >>= highAce
      where highAce hand = RoyalFlush |-
           hand ≡ StraightFlush (High (Face Ace))

straightFlush :: Query
straightFlush hand _ = (run `conjoin` sameSuit) hand >>=
                       return . StraightFlush

flush :: Query
flush hand x = let (HighCard hc r1 r2 r3 r4) = fromJust $ highCard hand x
               in  sameSuit hand >> return (Flush hc r1 r2 r3 r4)

straight :: Query
straight hand _ = run hand >>= return . Straight

The second argument of the Query type, which is a bag representation of the hand -- the rank of the cards and the count for each rank, was not used in the above rules, but becomes indispensable for the other rule findings, starting with the full house (3 of a kind and 2 of a kind in one hand):

fullHouse _ bag = let (a,3) = head bag
                      (b,2) = head (tail bag)
                  in  return (FullHouse (Threes a) (Twos b))

No, that's not right. The let-expression is not an assignment, it's an unification! For, after all, if the hand is not a full house, then the "assignment" fails in its "pattern match", so, not only are we attempting to fix the values of a and b but we are also propagating a success or truth value through that process. Hm, the "success of an assignment", what type would that be? Ah! Monadic, of course, and list compression compactly captures the concept of essayed assignment which we then distill (my much less cumbersome name for the standard library's listToMaybe function):

fullHouse :: Query
fullHouse _ bag = distill [FullHouse (Threes a) (Twos b)
                                | (a,3) ← bag, (b,2) ← bag]

It is almost criminally embarrassing on how easy this rule is to translate from the specification: "A full house is the distillation of a hand into three a's and two b's."⁵ From this understanding, the other hands fall out naturally:

fourofakind :: Query
fourofakind _ bag = distill [FourofaKind (Fours a) (High b) 
                                  | (a,4) ← bag, (b,1) ← bag]

threeofakind :: Query
threeofakind _ bag = distill [ThreeofaKind (Threes a) (High b) c
                                  | (a,3) ← bag, (b,1) ← bag,
                                    (c,1) ← bag, b > c]

twopairs :: Query
twopairs _ bag = distill [TwoPair (Twos a) (Twos b) (High c)
                                  | (a,2) ← bag, (b,2) ← bag,
                                    a > b, (c,1) ← bag]

onepair :: Query
onepair _ bag = distill [OnePair (Twos a) (High b) c d
                                  | (a,2) ← bag, (b,1) ← bag,
                                    (c,1) ← bag, b > c,
                                    (d,1) ← bag, c > d]

... and finally there's the catch-all for the "I'd better be good at bluffing" hand:

highCard :: Query
highCard hand _ = let [hc,r1,r2,r3,r4] = map settleRank hand
                  in  return (HighCard (High hc) r1 r2 r3 r4)

settleRank :: Card → Rank
settleRank (Card rank _) = rank

Now that we have the rules, we need simply write the marshalling code, the rule-finding loop, and the arbiter to complete our rule engine.

The marshalling code pre-processes the hand into a bag in order to facilitate n-of-a-kind rule findings:

let groups = group $ map settleRank cards
    cards = reverse (sort hand)
    counts = map length groups
    bag = zipWith (curry (first head)) groups counts
    [...]

The rule-finding loop applies the rules to the (processed) hand in order:

    [...]
    rules = [royalFlush, straightFlush, fourofakind,
             fullHouse, flush, straight, 
             threeofakind, twopairs, onepair,
             highCard]
    findings = map (λf . f cards bag) rules⁶
    [...]

And, finally, the arbiter in this case is very simple: it takes the first (highest ordered) rule-finding as the result.

    [...]
in  fromJust (msum findings)

With that, we have built the kernel of a complete rule-based system.

In this article, we demonstrated that Haskell, with standard extensions, can follow a process that constructs rules. This process not only matches the ease and simplicity of rule-building in Prolog, but it also has the benefit that these rules in Haskell have the type-correctness that provides a stronger degree of confidence in the rule-finding results.

End notes
¹	I must be getting older. Not too long ago, my refutation would have been more emphatic ... to the tune of: "Wrong!"
²	I say "for my sake" because I'm the guy you're going to be complaining about: "All I wanted him to do is just add this one rule set to the system, and he goes off and rewrites the entire system to do it!"
³	While you're at it, put all your debug statements into aspects (because `nl` should not even appear in core production code much less be the most frequently called "goal" in the system) and then have a complete(ly automated) unit test suite so that additions or deletions are entirely covered by this safety net, but those are whole ('nother) discussions onto themselves.
⁴	But why choose a functional programming language like Haskell? If Prolog nearly fits the bill, wouldn't a well-typed logic programming language, say, Mercury, or others, fair better than Haskell? The problems with most of these languages is that they fall into the research/academic ghetto. The user base is comprised of the language developers and maybe one or two others, and so the languages stagnate in their insularity. Haskell, and some other languages, including Prolog itself, have garnered enough outside attention and use to grow organically beyond their inventors' control, boundaries and strictures -- these languages retain their academic foundations but also gain a set of practical, useful, tools and extensions.
⁵	... cannot resist ... "or not two `b`'s" sigh
⁶	The Applicative style (see this paper) would have the list of functions applied to the list of arguments thusly ... `map uncurry rules <*> [(cards, bag)]` ... but I suppose that, in itself, opens up a new topic of discussion, which I will currently shunt to another day.

Composing functions with Arrows

2008-05-28T12:46:00.000-07:00

The Arrow class in Haskell is a generalization of the Monad class. Whereas a Monad type contains a value, and therefore is often used to represent state (in that the value captures the output of a function), an Arrow type represents the entire function, capturing both its inputs and outputs.

This is very Prolog-y. In Prolog, there are no functions, per se: the procedure's parameters (both input and output, if the procedure has any) are explicit in the declaration.¹ It's this total control of the procedure's environment that makes writing, e.g., aspects for Prolog a trivial exercise.

With Arrows, Haskell, which has always been friendly to function composition, receives another way of controlling data flow and composing functions. This topic is broad, diverse and general, and I am just starting down the path of exploring the Arrow class, so this entry will concentrate on only one aspect of the Arrow class, that is data flow through a composed arrow.

The problem comes up often enough: one wishes to dispatch some input through different functions and then marry the results for disposition by another function (if this sounds like neural nets or circuits, that's because those systems do just that). The usual way of going about this work is for the programmer to shepherd the data as it flows from function to function. However, the Arrow protocol provides tools to automate this shepherding. To provide a specific example of the above described problem, we will use problem 54 from Project Euler to illustrate: which hand of poker wins (with the problem statement listing the rules of what makes a hand of poker and the ranking of hands)?

To see which hand wins, first the hands must be classified to their type: high card, pair, two pairs, three of a kind, straight, flush, full house, four of a kind, straight flush and royal flush. We will concentrate on hands that are straights, flushes, straight flushes and royal flushes.²

Given a hand is a list of cards of the following type ...

data Face =  Jack | Queen | King | Ace deriving (Eq, Ord, Enum)
data N = Two | Three | Four | Five | Six | Seven | Eight
         | Nine | Ten deriving (Eq, Ord, Enum)
data Rank = N N | Face Face deriving (Eq, Ord)

data Suit = Diamonds | Clubs | Spades | Hearts deriving Eq

data Card = Card Rank Suit deriving Eq³

... and cards are typed as follows ...

data HighCard = High Rank deriving (Eq, Ord)

data Type = [...]
             | Straight HighCard
             | Flush HighCard Rank Rank Rank Rank
             [...]
             | StraightFlush HighCard
             | RoyalFlush deriving (Eq, Ord)

... and the cards are ranked in descending order, seeing if a hand is a straight is simply a check to see if all cards are a run:

run :: MonadPlus m ⇒ [Card] → m HighCard
run (Card rank _:cards) 
     = High rank |- descending (value rank) 
                               (map value cards)
     where descending _ [] = True
           descending x (card:t) = x - 1 ≡ card
                                   ∧ descending card t

... where the value returns the value (of the rank) of the card (Two ≡ 2, Three ≡ 3, ..., King ≡ 12, Ace ≡ 13), and the |- function [pron: "implied by"] converts a value to its MonadPlus equivalent based on the result of a predicate:

(|-) :: MonadPlus m ⇒ a → Bool → m a
x |- p | p         = return x
       | otherwise = mzero

A flush is a hand that has all cards of the same suit ...

sameSuit :: MonadPlus m ⇒ [Card] → m Suit
sameSuit (Card _ suit:cards) = suit |- all inSuit cards
    where inSuit (Card _ s) = s ≡ suit

... or in the mode of sameSuit a flush is a hand where every other card has the same suit as the first card.

So now we have functions that determine if a hand is a flush or if its a straight. Now, during the discussion, you may have been wondering at the return type of these functions. Why not simply return a truth value, as these are predicates on straights and flushes? If these functions simply tested only for straights and flushes (mutually-) exclusively, the return type of Bool is most appropriate, but we intent to use these tests for more than just that: we will be using these simple functions to build our tests for straight flushes and royal flushes, and their return types help in that eventuality.

The strength of the Arrow class comes into its own in the following development, as well.

First off, what are straight flushes and royal flushes, conceptually? A straight flush is a straight in the same suit with a discriminating high card (for, after all, 109876 beats 76543). A royal flush is a straight flush with an ace as the high card. Now it is clear that the return type of the test functions above need more information than what Bool conveys.

So, we need to process the hand through both run and sameSuit, obtaining positive results from both functions, and we need to retrieve the result from run either to ensure the hand is a royal flush (because the high card must be an ace) or to fix the value of the straight flush. The Arrow protocol has function, &&& [pron. "fan-out"] that splits an input and sends it off to two Arrow types for separate processing, so to determine a straight flush we start the test with ...

run &&& straight

... which gives the following results (with the Maybe type selected to represent the particular MonadPlus):

AKQJ10	`(Just (Face Ace), Just (Suit Spades))`
AKQJ10	`(Just (Face Ace), Nothing)`
AK762	`(Nothing, Just (Suit Spades))`
QQQ44	`(Nothing, Nothing)`

Now that we have those results (in the form of a tuple pair), we need simply to perform a logical-and over the different values to obtain a conjoined truth result and to retrieve the high card's value to determine the "blue-blooded"ness of the straight flush.

That solution gives us two problems to deal with:

I'm not aware of a logical-and operation for the MonadPlus types; but that doesn't matter because:

We're working with two different types of MonadPlus type values anyway.

So, I rolled my own conjunctive function, favoring the result of the run, given both tests resolve positively:

mand :: Monad m ⇒ m a → m b → m a
x `mand` y = y >> x >>= return

Given the above definition of mand and introducing the composition function of the Arrow protocol, >>>, we can now write the computation that determines a straight flush and returns its high card:

run &&& sameSuit >>> uncurry mand

In fact, this pattern: f &&& g >>> uncurry mand⁴ neatly captures the logic programming paradigm of goal-seeking via conjunction, so it deserves it's own apt abstraction:

conjoin :: Monad m ⇒ (a → m b) → (a → m c) → a → m b
conjoin f g = f &&& g >>> uncurry mand

So, now we have the tools available to discriminate a hand's type along the straight or royal flush -- the straight flush simply returns the type with the high card value ...

straightFlush :: [Card] → Maybe Type
straightFlush hand = (run `conjoin` sameSuit) hand >>=
                     return . StraightFlush

... and a royal flush is a straight flush with a guaranteed high ace:

royalFlush :: [Card] → Maybe Type
royalFlush hand = straightFlush hand >>= highAce
   where highAce kind
           = RoyalFlush |- kind ≡ StraightFlush (High (Face Ace))

Note the complementary rôles of conjoin and >>= [pron. bind]: conjoin marries two truth values (emphasizing the first), and >>= forwards a truth value for disposition. Due to the monadic nature of these functions, a false result (or failure) at any point in the computation aborts it, so these nondeterministic functions are very well-behaved: what is returned is either Just a straight flush or a royal flush if and only if every test is true along the way, or Nothing if even a single test fails.

In summary, this particular aspect of the Arrow protocol that captures the totality of functions and simplifies the control of data flow gives a particularly powerful and flexible set of tools to the user, combining this flexibility with (Arrow) composition and the existing Monad and MonadPlus facilities allows a programming style as simple, declarative and powerful as the logic-programming paradigm.

¹	Further distancing Prolog procedures from Haskell functions, the outcome of a procedure is not an "output" but its validity, or truth value -- how very un-Haskell-y!
²	But seriously! A royal flush? How many of you have every drawn that hand? There should be some special rule for drawing a royal flush, like: you get a life-time supply of marzipan loaded into the trunk of your brand new Bentley parked at your vacation home in St. Croix.
³	Note that in poker there is no precedence of suits (unlike in other card games, like Contract Bridge), so `Suit` is not an `Ord` type. This means, that since the `Card` type contains a `Suit` value, it, too, is not ordered ... if it were, then the situation would arise where a high card hand of 109... would lose to a high card hand of 106... which is patently not within the rules of poker.
⁴	In fact, the pattern `foo &&& bar >>> uncurry quux` deserves and has its own article which very prettily describes and illustrates graphically what this pattern does.

Monoid use

2008-05-28T04:12:00.000-07:00

I've been reading a bit about Monoids, which are a generalization of the MonadPlus specialization of the Monad class. The generalization of Monoids is that whereas a particular Monad type carries some (hidden) value, a Monoid type has no such requirement.

Firstly, what is a Monoid type? It is something that has an empty representation (mempty :: a) and has the property that allows two values to be joined (appended) to form a new value (mappend :: a → a → a). This protocol sounds very much like the one for MonadPlus types, doesn't it? It does, indeed, and with good reason, for every MonadPlus type is also a Monoid type:

instance MonadPlus m ⇒ Monoid (m a) where
     mempty  = mzero
     mappend = mplus

What are some examples of Monoid? Well, of course, the types that are MonadPlus types, like Maybe and specified list types (but with an important caveat: the generalized list container must be specialized to contain some particular type a). But besides these, Monoid gives us more types that do not fit within the MonadPlus protocol, for example, and importantly, integrals under addition or multiplication.

Ah! So if one were, say, doing an operation with some kind of list and then doing the exact same kind of thing, but simply marking results (counting, as [brilliantly!] demonstrated by the Peano series, is operating on integers under addition) without the Monoid abstraction, we would need to write two separate procedures (in the infamous style of copy-and-waste, er, -paste) to work with the two separate data types, but with Monoid we can have simply one procedure working with the Monoid type, giving us some measure of polytypic expressiveness. This brings us to where we were at the end of the previous entry on factorization, where we had developed a unifying function for factorization (where its rôles changed depending on what seed value it was given: it returned the factors when given a list or returned a count of the factors when given an integer). Recall that our helper function, mkadder, needed to be supplied with a translator function for the individual values processed and a concatenator function to tally those translated values:

showfactors x = factors x (mkAdder return mplus) []
countfactors x = factors x (mkadder (const 1) (+)) 0

The first using function, showfactors seized the advantage that lists are MonadPlus types, but the second, countfactors, could not do the same because integers are not monadic (they are not (polymorphic) containers), so this function had to provide its own versions of translation and concatenation.

This problem goes away, however, since both these particular types are Monoid types, right? Yes, well, there's the issue of how to enforce this relation — a unspecialized list is not a Monoid type, nor are integers, in general. For this particular case, we must demonstrate that our particular data are of the Monoid class (a list of integer for the former and integers under addition for the latter).

So, what needs to be done is that these types need to be declared instances of the Monoidic domain by injected their values into that domain (thanks to Dirk Thierbach's explanation):

class Injector m where
    inject :: Integral a ⇒ a → m a

instance Injector [] where
    inject x = [x]

instance Injector Sum where
    inject x = Sum 1

The above instance declarations do just that, making an injector on generalized lists one that translates some integral value into a specified (i.e. monoidic) list and making an injector on (generalized) sums one that translates some integral value (again) into a specified (again, monoidic) sum -- in this case the value is always translated into 1, because we are summing the number of factors (each factor adding 1 to the total number of factors), not the value of factors.

With these instances, we can now employ the protocol of Monoid to generalize the mkadder function. Recall its definition ...

mkadder :: Integral a ⇒ 
              (a → b) → (b → b → b) → a → a → (b → b) 
mkAdder f g y z = g (if   y ≡ z
                     then f y
                     else g (f y) (f z))

... where f is the translation function and g is the concatenation function. So, what mkadder does is to provide a concatenator for either just one of the values (if both values are the same) or for both values.

Now, we add the properties of the Injector as well as those of the Monoid to get a new mkadder function that can stand alone needing neither a translator nor a concatenator to be provided from using functions ...

mkadder :: (Injector m, Monoid (m a), Integral a) ⇒
              a → a → (m a → m a) 
mkAdder y z = mappend (if   y ≡ z 
                       then inject y 
                       else inject y `mappend` inject z))

... where the generic functions f and g are replaced, respectively, by the inject function from the Injector class and the mappend function from the Monoid class. Note, also that the type-relation that was unspecific in the previous version, (a → b), now has an explicit relation, (a → m a), thanks to the relation of the types between the Injector and Monoid classes. This relationship gives us a weak equivalent of a functional dependency. With this change in place, the using functions now no longer need to specify these functions, so they, in turn, simplify to:

showfactors x = factors x mkAdder []
countfactors x = getSum (factors x mkadder (Sum 0))

So, if you find yourself doing the same thing to very different types, and they all are not monadic, then perhaps the monoidic form may give the generality to encode those disparate types under one solution.

Optimizing Factorization

2008-05-24T15:43:00.000-07:00

I've been working my way through the problems hosted by Project Euler. Usually, using a naïve approach coupled with efficient nondeterminism suffices (oh! don't other problem solvers wish they had the MonadPlus in their semantics when tackling the now-trivial pandigital problems!), but I ran into a snag when I was factoring large triangular numbers.

The problem was my naïveté, of course.

My original version of factors proceeded thusly ...

factors :: Integral a ⇒ a → [a]
factors x = filter (λy . x `rem` y ≡ 0) [1..x]

... which is straightforward enough. One can't get any simpler than: "Keep ('filter') all the numbers from 1 to x that divide x with no remainder"!

Simple? Yes. Naïve? Yes. For small numbers, this factorization algorithm did just fine, even for the 384^th triangle, 73920, this algorithm found the 112 factors in a blink. The problem appeared when doing a (triangular) search along the Natural number line for an unknown, large, triangle. The factorization algorithm is linear, and combining it with a (nearly) linear search makes the entire activity quadratic. Twenty-six hours after I began my search ("find the first triangular number with more than 500 factors") the algorithm was still going with no solution.

There must be a better way to go about this. And, of course, there are more than a few ways, some of which you can pay for, but none, on the top of the search tree that appeared simple enough to comprehend and to implement in a reasonable time.

Fortunately, there also exists an obvious sub-linear solution: if we are given in the linear progression [1..x] at the current index, y, that y is a factor of x, then obviously ...

z where z = x / y

... is also a factor. Not only that, but, since we are progressing linearly, z now becomes the upper bound in the factorization algorithm. The fix-point of the algorithm described gives us a new, much more efficient, factorization ...

factors x = factors' 2 (x, [1,x])
     where factors' y res@(top, ans) | y ≥ top = ans
                 | otherwise = factors'' (x `divMod` y) y res
           factors'' (newtop, 0) y (oldtop, ans)
                     = factors' (succ y) (newtop, y:oldtop:ans)
           factors'' _           y res
                     = factors' (succ y) res

... Much more efficient? Yes. Self-describing? Not so much. Also, there's now a subtle error introduced by assuming all factors are unique, for ...

> factors 25 → [5,5,1,25]

... duplicates are introduced when factoring squares. Testing uniqueness adds its own complexity:

factors x = factors' 2 (x, [1,x])
     where factors' y res@(top, ans) | y ≥ top = ans
                 | otherwise = factors'' (x `divMod` y) y res
           factors'' (newtop, 0) y (oldtop, ans)
                     = factors' (succ y) (newtop, addin y oldtop ans)
           factors'' _           y res
                     = factors' (succ y) res
           addin x y list | x &equiv y     = x:list
                          | otherwise = x:y:list

Complexity on top of complexity! This goes against my grain (as well as Richard O'Keefe's as you see in the side-bar quote), but is it worth it?

> sort (factors (triangle 12375)) → [1,2,3,...572 others...,76576500]

Yes, as the above interaction took no noticeable time, whereas before no solution was available after a day's worth of computation. So this optimized factorization algorithm is "good enough" for the task at hand, for I did solve the problem using that algorithm.

But, returning to the fix-point, which more than generalizes recursive algorithms -- it can be used to think of algorithms, qua algorithms, more generally. In this particular case, I have no desire to view every one of the 576 factors of this triangular number. No, I simply wish to ensure that there are more than 500 factors, no matter what those factors are. So, in the large, something like a countfactors (that simply returns the number of factors, instead the list of all the factors) is more desirable. How are we to go about writing such an algorithm? Most coders, I regret to observe, would punt to the copy-and-paste style of coding, as the desired changed is buried deeply within the algorithm. Not only that, but the type signature of the function varies with our alternatives: in what we've developed so far, the algorithm returns a list, but what we wish to have instead is (only one) number.

Fortunately, Dirk Thierbach introduced me to this particular use of the fix-point -- we simply extract the engine of computation into an external function. So now we have two functions that collapse into one line each ...

showfactors :: Integral a ⇒ a → [a]
showfactors x = factors x (λ y z ans . if y ≡ z then y:ans else y:z:ans) []

countfactors :: Integral a ⇒ a → a
countfactors x = factors x (λ y z ans . if y ≡ z then 1 + ans else 2 + ans) 0

... with factors being (slightly) modified to accept the new functional argument and base case:

factors :: Integral a ⇒ a → (a → a → b → b) → b → b
factors x adder ans = factors' 2 (x, adder 1 x ans)
       where factors' y (tot, ans) | y ≥ tot = ans
                       | otherwise  = factors'' (x `divMod` test) y (tot, ans)
             factors'' (tot, 0) y (_, ans)
                     = factors' (y+1) (tot, adder y tot ans)
             factors'' _ _ y ans
                     = factors' y ans

With this approach, the return type depends on the calling function's use and is threaded throughout the utility function, factors, by the adder computation engine.

One final note: the λ-terms in both calling functions showfactors and countfactors are also of the same structure, so we can again perform surgery, extracting the engine from the structure:

mkAdder :: Integral a ⇒ (a → b) → (b → b → b) → a → a → (b → b) 
mkAdder f g y z = g (if y ≡ z then f y else g (f y) (f z))

Now, anyone who's been working with monads for more than an brief period will see the b type as monadic and the functional type (a → b) as a lifting function (return) and the composition function, g, as monadic addition. And, as it turns out, this concept fits very nicely with the new implementation ...

showfactors x = factors x (mkAdder return mplus) []
countfactors x = factors x (mkadder (const 1) (+)) 0

With these new implementations, how much does factors need to change? Not one bit. Functional purity: why can't all programming languages have this? And with this generalization, I was able to achieve the desired result:

> countfactors (triangle 12375) → 576

Now it is known that both lists of some type (in this case integers) and also integers under addition are monoids. Given that, mkAdder can be further simplified. Also, the if-then-else is easily replaced by the Either type and proper use of arrows, but these are discussions for another day.

Guarded Choice with MonadPlus

2008-05-16T17:56:00.000-07:00

In the previous article, I introduced the MonadPlus class and three examples of monads that allow for non-determinism in programming (Maybe and the list data type, both of which are MonadPlus types and Either, which can be coerced into a MonadPlus type). These types were introduced, but besides showing (unexplained) examples and minimal explanation of the Maybe lookup example, there is not much there to show how to program in a declarative nondeterministic manner. Let's rectify that. First, we'll show how to program nondeterministically and narrow the options down with guard. We will be using the standard nondeterministic "Hello, world!" problem, that is: solving the cryptarithmetic problem ...

SEND + MORE = MONEY

... by iteratively improving the efficiency of the solution.

First up, list compression is a powerfully expressive programming technique that so naturally embodies the nondeterministic programming style that users often don't know they are programming nondeterministically. List compression is of the form:

[ x | qualifiers on x]
where x represent each element of the generated list, and the qualifiers either generate or constraint values for x

Given the above definition of list compression, writing the solution for our cryptarithmetic problem becomes almost as simple as writing the problem itself:

[(s,e,n,d,m,o,r,e,m,o,n,e,y) | s ← digit, e ← digit, n ← digit,
                               d ← digit, m ← digit, o ← digit,
                               r ← digit, y ← digit,
                               s * 1000 + e * 100 + n * 10 + d
                               + m * 1000 + o * 100 + r * 10 + e
                               ≡ m * 10000 + o * 1000 + n * 100
                                  + e * 10 + y]
   where digit = [0..9]

Easy, but when run, we see that it's not really what we needed for the answer is ...

[(0,0,0,0,0,0,0,0,0,0,0,0,0),(0,0,0,1,0,0,0,0,0,0,0,0,1),...]

... and 1153 others. No, we wish to have SEND + MORE = MONEY such that S and M aren't zero and that all the letters represented different digits, not, as was in the case of the first solution, all the same digit (0). Well, whereas we humans can take some obvious constraints by implication, software must be explicit, so we need to code that S and M are strictly positive (meaning, "greater than zero") and that all the letters are different from each other. Doing that, we arrive at the more complicated, but correct, following solution ...

[(s,e,n,d,m,o,r,e,m,o,n,e,y) | s ← digit, s > 0,
                               e ← digit, n ← digit, d ← digit,
                               m ← digit, m > 0,
                               o ← digit, r ← digit, y ← digit,
                               different [s,e,n,d,m,o,r,y], 
                               num [s,e,n,d] + num [m,o,r,e]
                                 ≡ num [m,o,n,e,y]]
   where digit = [0..9]
         num = foldl ((+).(*10)) 0
         different (h:t) = diff' h t
         diff' x [] = True
         diff' x lst@(h:t) = all (/= x) lst && diff' h t

A bit of explanation -- the function num folds the list of digits into a number. Put another way ...

num [s,e,n,d] ≡ ((s * 10 + e) * 10 + n) * 10 + d

... and the function different, via the helper function diff', ensures that every element of the argument list are (not surprisingly) different -- a translation of diff' is ...

diff' x [] = True "A list is 'different' if there is only one number"
diff' x lst@(h:t) = all (≠ x) lst && diff' h t "A list is 'different' if one of the numbers is different than every other number in the list and if this is true for all the numbers in the list"

... and after a prolonged period [434 seconds], it delivers the answer:

[(9,5,6,7,1,0,8,5,1,0,6,5,2)]

Okay! We now have the solution, so we're done, right? Well, yes, if one has all that time to wait for a solution and is willing to do tha waiting. However, I'm of a more impatient nature: the program can be faster; the program must be faster. There are few ways to go about doing this, and they involve providing hints (sometimes answers) to help the program make better choices. We've already done a bit of this with the constraints for both S and M to be positive and adding the requirement that all the letters be different digits. So, presumably, the more hints the computer has, the better and faster it will be in solving this problem.

Knowing the problem better often helps in arriving at a better solution, so let's study the problem again:

 SEND
+MORE
MONEY

The first (highlighted) thing that strikes me is that in MONEY, the M is free-standing -- its value is the carry from the addition of the S from SEND and the M from MORE. Well, what is the greatest value for the carry? If we maximize everything, then the values assigned are 8 and 9, then we find the carry can at most be 1, even if there's carry over (again, of at most 1) from adding the other digits. That means M, since it is not 0, must be 1.

What about for S, can we narrow its value? Yes, of course. Since M is fixed to 1, S must be of a value that carries 1 over to M. That means it is either 9 if there's no carry from addition of the other digits or 8 if there is. Why? Simple: O cannot be 1 (as M has taken that value for itself), so it turns out that there's only one value for O to be: 0! We've fixed two values and limited one letter to one of two values, 8 or 9. Let's provide those constraints ("hints") to the system.

But before we do that, our list compression is growing larger with these additional constraints, so let's unwind into an alternate representation that allows us to view the smaller pieces individually instead of having to swallow the whole pie of the problem in one bite. This alternative representation uses the do-notation, with constraints defined by guards.

A guard is of the following form:

guard :: MonadPlus m ⇒ Bool → m ()

What does that do for us? Recall that MonadPlus kinds have a base value (mzero) representing failure and other values, so guard translates the input Boolean constraint into either mzero (failure) or into a success value. Since the entire monadic computation is chained by mplus, a failure of one test voids that entire branch (because the failure propagates through the entire branch of computation).

So, now we are armed with guard, we rewrite the solution with added constraints in the new do-notation.

do let m = 1
       o = 0
   s ← digit
   guard $ s > 7
   e ← digit
   n ← digit
   d ← digit
   r ← digit
   y ← digit
   guard $ different [s,e,n,d,m,o,r,y]
   guard $ num [s,e,n,d] + num [m,o,r,e] ≡ num [m,o,n,e,y]
   return (s,e,n,d,m,o,r,e,m,o,n,e,y)
        where digit = [2..9]

Besides the obvious structural difference from the initial simple solution, we've introduced some other new things --

When fixing a value, we use the let-construct.

As we've grounded M and O to 1 and 0 respectively, we've eliminated those options from the digit list.

Since the do-notation works with monads in general (it's not restricted to lists only), we need to make explicit our result. We do that with the return function at the end of the block.

What do these changes buy us?

[(9,5,6,7,1,0,8,5,1,0,6,5,2)] returned in 0.4 seconds

One thing one learns quickly when doing logic, nondeterministic, programming is that the sooner a choice is settled correctly, the better. By fixing the values of M and O we entirely eliminate two lines of inquiry but also eliminate two options from all the other following choices, and by refining the guard for S we eliminate all but two options when generating its value.

In nondeterministic programming, elimination is good!

So, we're done, right? Yes, for enhancing performance, once we're in the sub-second territory, it becomes unnecessary for further optimizations. So, in that regard, we are done. But there is some unnecessary redundancy in the above code from a logical perspective -- once we generate a value, we know that we are not going to be generating it again. We know this, but digit, being the amb operator doesn't, regenerating that value, then correcting that discrepancy only later in the computation when it encounters the different guard.

We need the computation to work a bit more like we do, it needs to remember what it already chose and not choose that value again. We've already use memoization when we implemented the Fibonacci sequence and the Ackermann function with the State monad; so let's incorporate that into our generator here.

What we need is for our amb operator to select from the pool of digits, but when it does so, it removes that selected value from the pool. In a logic programming language, such as Prolog, this is accomplished easily enough as nondeterminism and memoization (via difference lists) are part of the language semantics. A clear way of dissecting this particular problem was presented to me by Dirk Thierbach in a forum post on comp.lang.haskell, so I present his approach in full:

I need both state and nondeterminism, so I have to combine the state monad and the list monad. This means I need a monad transformer and a monad (you need to have seen this before, but if you have once, it's easy to remember).

The state itself also has to be a list (of candidates).

So the final monad has type StateT [a] [] b.

I need some function to nondeterministically pick a candidate. This function should also update the state.

Played around a short time with available functions, didn't get anywhere.

Decided I need to go to the "bare metal".

Expanded StateT [a] [] a into [a] → [(a,[a])], then it was obvious what choose should do.

Decided the required functionality "split a list into one element and rest, in all possible ways" was general enough to deserve its own function.

Wrote it down, in the first attempt without accumulator.

Wrote it down again, this time using an accumulator.

With this approach presented, writing the implementation simply follows the type declaration:

splits :: Eq a ⇒ [a] → [(a, [a])]
splits list = list >>= λx . return (x, delete x list)

Although, please do note, this implementation differs significantly from Dirk's, they both accomplish the same result. Now we lift this computation into the State monad transformer (transformers are a topic covered much better elsewhere) ...

choose :: StateT [a] [] a
choose = StateT $ λs . splits s

... and then replace the (forgetful) digit generator with the (memoizing) choose (which then eliminates the need for the different guard) to obtain the same result with a slight savings of time [the result returned in 0.04 seconds]. By adding these two new functions and lifting the nondeterminism into the StateT we not only saved an imperceptibly few sub-seconds (my view is optimizing performance on sub-second computations is silly), but, importantly, we eliminated more unnecessary branches at the nondeterministic choice-points.

In summary, this entry has demonstrated how to program with choice using the MonadPlus class. We started with a simple example that demonstrated (naïve) nondeterminism, then improved on that example by pruning branches and options with the guard helper function. Finally, we incorporated the technique of memoization here that we exploited to good effect in other computational efforts to prune away redundant selections. The end result was a program that demonstrated declarative nondeterministic programming not only fits in the (monadic) idiom of functional program but also provides solutions efficiently and within acceptable performance measures.

Choice with Monads: List, Maybe, Either

2008-05-14T15:31:00.000-07:00

We've seen up to now what monads are and how they can be useful in simple ways, such as for heavy lifting on recursive addition. So, monads are useful for housekeeping when you have more work than a computer could handle in a straightforward manner. This work is called deterministic, meaning that the computation occurs in only one way. As we have seen, monads can be helpful with this kind of computation. But monads can be helpful with nondeterministic computations, or computations that proceed along multiple possible paths, as we shall see.

Haskell comes with three kinds of monads that have been used specifically for nondeterministic computation: the Maybe monad, the list data type and, a new one, the Either monad.

We saw the first one in the previous post: the Maybe monad. This monad type has two instances: Nothing and Just x (where x is the specific value of the computation). The Maybe monad is illustrated by the two dialogues below:

Scenario 1
Waiter:	How is the pork chop, can I get you anything to go with that?
Custamah:	Oh, `Nothing` for me, thanks.
Waiter:	Wonderful, enjoy your meal.

Scenario 2

Waiter:	How is the pork chop, can I get you anything to go with it?
Custamah:	Oh, `Just` a small bowl of applesauce, please?
Waiter:	Sure, I'll bring that right out.

The waiter in the above two scenarios doesn't know exactly what the customer will want, but that waiter is pretty sure the customer will ask for Nothing or for Just something, and these options describe the Maybe monad type.

Another example of this kind of monad is the list data type. But whereas the Maybe monad allows two options (the answer or failure), the list data type (a monad) allows multiple answers (including no answers, which is represented by the empty list). These kinds of monads form a protocol called the MonadPlus class, just as the more general monad data types form the more general protocol of the Monad class, and just like regular monads, conform to a set of laws.

First, let us specify and explain what the MonadPlus protocol is. All MonadPlus types must have the following two properties defined:

mzero :: m a — the base, or usually interpreted as fail, value; and,
mplus :: m a → m a → m a — a function that chooses a success value when offered two values

For the Maybe MonadPlus type the above properties are defined as follows:

mzero = Nothing
Nothing `mplus` b = b
a       `mplus` b = a

In other words, Nothing is the failure case, and mplus tries to choose a non-Nothing value (roughly: "If a is Nothing, pick b; otherwise pick a." Here's a question for you: what happens when both a and b are Nothing, and for what reason?) Note the interesting semantics of mplus — it is not at all addition, as we expect, for:

Just 3 `mplus` Just 4 = Just 3

Recall that if we wish to do monadic addition, we need to define such an operator.

madd :: (Monad m, Num a) ⇒ m a → m a → m a
madd = liftM2 (+)
Just 3 `madd` Just 4 = Just 7

So, now madd has the triple meaning here: it is not mplus (which is not addition), it is addition for monads containing numbers, and it either heightens awareness or annoys the cause of "MADD". Got all that?

The Maybe type has a special handler, called maybe. Its type signature is:

maybe :: b → (a → b) → Maybe a → b

What does this function do? Well, we've already seen it in action with the monadic Ackermann and Fibonacci solutions. One can read the arguments from right to left, to get the feel of an if-then-else: if the last argument is Just a, then pass a to the second argument (which is a function that converts an a to the proper return type); else execute the first argument. A very compact and useful function when working with Maybe types.

The second most commonly used data type used for non-deterministic computation is the list MonadPlus data type. It has an interesting variation from the Maybe definition:

mzero = []
mplus = (++)

In other words, the empty list ([]) is the base (failure) case, and mplus here actually is addition ('concatenation', to be technically correct); addition, that is, in the list-sense. But it all works out, particularly when it comes to the base cases, for:

[3] `mplus` [] = [3]
Just 3 `mplus` Nothing = Just 3

But, on the other hand, mplus is different when handling non-base cases for the Maybe and list monad types, for:

[3] `mplus` [4] = [3, 4]
Just 3 `mplus` Just 4 = Just 3

But this difference is consistent with the different types: the list monad allows for multiple solutions, whereas the Maybe monad allows only one.

The list data type has too many special functions associated with it to review in this post. I recommend a review of the Haskell online report to get a taste of list's rich functionality, and then read Eric Kidd's post on backtracking with monads for some insights into using list monads in nondeterministic programming.

The third data type that is used, albeit less frequently, for non-deterministic computation is the Either data type. It's structure is as follows:

data Either a b = Left a | Right b

The way Either operates is that it offers a mutually-exclusive choice. For example, little Isabel sits to my Left and her até Elena Marie sits to my Right, so at 4 p.m. I must choose Either one to serve tea first: Left Isabel or Right ElenaMarie.

The interesting distinction of the Either monad to MonadPlus types such as the list data type and the Maybe monad is that both options are weighed equally, or, more to the point, neither is considered to be the base case. This means that Either, qua Either, is not in the MonadPlus class. With this caveat, can the Either type be used for non-deterministic computation? Yes, absolutely!

Not only can the Either type be used in its basic monadic form, but it also can be coerced into the MonadPlus class. How? It's simple, really. By simply choosing one of the branches to be the base (the Haskell library designers chose Left), the Either type now conforms to that protocol. The convention assigns the error message (a String) to the Left and the value sought is assigned to the Right one. This rather reduces Either to a glorified, error-handling, Maybe, and that is how it is used in every-day Haskell code for the most part.

The Either monad also has a special handler, either, with the type signature of:

either :: (a → c) → (b → c) → Either a b → c

This function is in the same vein as the Maybe handler, but complicated by the fact that maybe has only one (success) type to handle, whereas this function has two possible types it deals with — either's type translates as: if the answer from the third argument (Either a b) is Left a, then feed a to the first argument (a function that converts the input value of type a to the output of type c), but if the answer from the third argument is of type Right b, then feed b to the second argument (a function that converts the input value of type b to the output of type c).

What we've seen in this entry is an introduction to the MonadPlus class and three examples of monads that allow for choice, Maybe, the list data type and Either, and saw an example for each which demonstrated their ability to code with choice.

The next entry will further explore the MonadPlus class and some of its powerful functions, such as msum and guard, and how the MonadPlus class allows us to code in a declarative nondeterministic style.

No "fib"bing; getting into the monad groove

2008-05-14T15:28:00.000-07:00

The title is groan-inducing, as all my "jokes" are. I guarantee it: once you've finished reading this entry, reread the title, and you won't be able to stop from groaning.

The Fibonacci series goes as follows: 0,1,1,2,3,5,8,13..., or put another way, the current number is obtained by adding the previous two numbers. It is useful for many things, as its limit is the golden ratio, found in nature (the spiral of some crustaceans and the population growth of rabbits [they must be stopped!]) and in artifice (windows, painting, doors, buildings follow the width and height of this ratio)).

Any fibonacci number can be easily computed from the following formula ...

fib :: Integer → Integer
fib n | n ≡ 0     = 0
      | n ≡ 1     = 1
      | otherwise = fib (n-1) + fib (n-2)

... that is, easily computed if this world were purely mathematical, including the caveat that any computable function could be instantly computed. Run on a computer, fib 25 slows noticeably and fib 50 may as well describe the halting problem, because I wasn't going to wait around for it to terminate.

Note the similarity between the computation of the Fibonacci series to the computation of the Ackermann table. They are not the same kind of problem, mind you, as the Ackermann is not primitively recursive; the Fibonacci is "only" doubly (branching) recursive. But they are similar enough in that they can be solved in similar ways. Given that the current Fibonacci number is the sum of the previous two Fibonacci numbers, we need only a (reversed) list to memoize the previous results, so the above sequence becomes:

[..., 13, 8, 5, 3, 2, 1, 1, 0]

and the "next" Fibonacci number would be simply the first two elements of this list (21, in this case). But how do we know where we are in the sequence? Easy: the length of this list tells us where we are, and in this case, the list has 8 elements, meaning the "next" Fib is 9th in the sequence.

So, turning to monads with this list structure for memoization, the code falls out as follows:

fib :: Int → FibS
fib n = get >>= λmem . maybe (fib' n >>= update)
                             return
                             (gimme mem n)

So, fib is now simply a decision: "Do I have the fib requested in the list?" "Yes: gimme it and return it" or "No: compute it and then update the list"

The list is a very slight variation on a regular list type, as we choose to carry around its length (as opposed to recomputing it at each iteration), and we lift this new data type into the State monad (as we did with the Map data type for our Ackermann monad optimization):

data Mem = Mem [Integer] Int
type FibS = State Mem Integer

The actual computation function is lifted into the monadic form with very little variation ...

fib' :: Int → FibS
fib' n | n ≡ 0     = return 0
       | n ≡ 1     = return 1
       | otherwise = liftM2 (+) (fib (n - 1)) (fib (n - 2))

... where monadic addition, liftM2 (+), replaces addition in the usual sense (recall the spot of bother we had "adding" Thing One to Thing Two), and where the plain numbers are lifted into the monad with return. In brief, the substance is now monadic but the structure is the same as our original, plain, fib.

The other housekeeping functions are new for the monadic solution, but what one would expect. The update follows in the same vein as the one for the ackermann monad:

update :: Integer → FibS
update n = do (Mem lst len) ← get
              put (Mem (n:lst) (len + 1))
              return n

An interpretation of the update function is that it is the identity function with the side-effect that it remembers the result that it returns.

The only other function is the self-describing gimme which retrieves a previously-computed fibonacci number from memory:

gimme :: Mem → Int → Maybe Integer
gimme (Mem (h:t) len) n | len ≡ n   = Just h
                        | len > n   = let x = (len - 1) - n
                                      in Just (t !! x)
                        | otherwise = Nothing

This gimme function uses the Maybe monad and its functionality, saying "If I have the value already computed [If the list length is equal to or greater than the requested index], then return Just that value; otherwise I've got Nothing, so you need to compute that value."

In summary, we've decorated the naïve fibonacci algorithm with some memory and three new functions (one manager and two support functions). What is the payoff?

Ready> fib 1500
[no delay]
135511256685631019516369368671484083777860107124184972421335
431532214873108735287506122593540357172653003737788143473202
576992570823565500453499141029242495959974839822286992875272
419318113250950996424476212422002092544399201969604653214384
983053458933789325853933815390935494792961948008381459961871
22583354898000

Ready> fib 50000
[4 second delay]
[10615 digits]

Ready> fib 60000
[2.5 second delay]
*** Exception: stack overflow

These results are a great step forward over the naïve fib implementation (which essentially froze at fib 50) and even memoized implementation reported elsewhere (which ran out of memory after fib 1450).

Huzzah! then for efficient program representation in Haskell and monadic code.

Oh! my acking monad!

2008-05-14T15:24:00.000-07:00

So, we just saw, after reams of paper on proving in inscrutable detail the three monadic laws, that after all that, we see that using them is pretty easy. Fancy that, Hedda!

Haskell does provide several different kinds of monads for various uses, but sometimes one must roll one's own to fit the current need. I was exploring the ackermann function, curious to know what A_4,2 looked like [oh, yes, 19730 digits in all its (gory) glory -- I went there!] (other than the cop-out of 2⁶⁵⁵³⁶-3 that is listed in Wikipedia), and whether my computer could calculate and display that value [obviously it could, but it took some work (see below) to arrive at that point]. The ackermann function written in Haskell looks very much like its representation in standard mathematical notation:

a :: Integer → Integer → Integer
a m n | m ≡ 0           = n + 1
      | m > 0 ∧ n ≡ 0   = a (m - 1) 1
      | m > 0 ∧ n > 0   = a (m - 1) (a m (n - 1))

The "problem" with the Ackermann function is that even though it is easy to write, the recursion required to arrive at a solution from even small (single digit) inputs is staggering. My computer staggered and then killed the computation in mid-process (too bad Redjak didn't have that option). The Ackermann function, being not primitively recursive, is also highly redundantly recursive, so it would be nice to provide "hints" to the program, something like: "Oh, you've already computed A_3,1 to be 13, so you don't need to recompute that entire branch any more."

This "hinting" has a name in computer science; it's called "memoization", and Haskell provides the State monad that can be used to cover that functionality quite nicely. As we're computing the values that build up the solution, we put the smaller-indexed solutions into a dictionary, something like:

A_3,1	=	13
A_2,2	=	7
A_2,1	=	5
... and so forth ...

Such a dictionary in Haskell is called a Map, because we are mapping from the "word" (the indices of the Ackermann function) to the "definition" (the solution)...

type Index = (Integer, Integer)
type AckMap = Map Index Integer

... and we wrap that Map with the State monad ...

type AckMapS = State AckMap Integer

... where AckMapS uses the AckMap dictionary to provide the preexisting (partial) solution, or, given there's none yet, populates the solution calculated (the Integer) into the dictionary at the current Index. Simple, yes? So, all we need is an utility function that does the lookup or updates the state ...

ackify :: Integer → Integer → AckMapS
ackify m n = get >>= λma . maybe (a' m n >>= update m n) 
                                 return
                                 (Map.lookup (m, n) ma)

... the update function that actually does the housekeeping ...

update :: Integer → Integer → Integer → AckMapS
update m n ans = do mappo ← get
                    put (Map.insert (m, n) ans mappo)
                    return ans

... so that our monadic version of the ackermann function is as follows:

a' :: Integer → Integer → AckMapS
a' m n | m ≡ 0           = return (n + 1)
       | m > 0 ∧ n ≡ 0   = ackify (m - 1) 1
       | m > 0 ∧ n > 0   = ackify m (n - 1) >>= ackify (m - 1)

which looks very much the same as the original function, with calls to a being replaced by calls to the lookup-or-update ackify function and function composition (e.g. a (m - 1) (a m (n - 1))) being replaced by the monadic composer, >>=. So, from the above demonstration we see that monads are not only easy to use, but also easy to "roll your own" and integrate into preexisting non-monadic code without much fuss.

Critique

Although the incorporation of the State monad dramatically speeds processing solutions and makes some solutions computable that were unreachable under the naïve approach, there are at least two better generalizations:

Use the fixpoint (or the Y-combinator) of the ackermann function so that one can now decorate the engine of computation without altering its structure at all! Incredible! So instead of using a monad to abstract stateful decoration of computations, the fixpont can be used to abstract any decoration of computation!

Use the compiler to change the code, instead of having it programmed in. Many functional language compilers have the option to memoize computations automagically. So, instead of writing code that memorizes partial results, the compiler intercepts the computation, replacing computation with previously calculated values (or running the computation if no such value exists and then storing that result into the runtime). No extra coding; no "troublesome" monads.

Critique on the critique

On the other hand ("there are five fingers", as my favorite Mother-in-law enjoys rejoining),

The fixpoint solution is more general and more elegant, but being more general suffers in a slight decrease in efficiency: it more than likely will run more slowly than the specialized monadic state solution

With an explicit encoding of state, the programmer has direct say into what is memoized and what is not, but with a compiler directive, everything is memoized. Since the Ackermann function can be represented by simple functions for m < 4, the map can be replaced by a faux-map for those values, reducing the memory footprint of memoization to only a couple of cells for m == 4 (as opposed to over 150,000 cells for m == 4 and n == 1 using the naïve memoization scheme).

... so the above described solution may be "good enough" for the task at hand, after all. Put another way, when I said I was wrong, I might have been wrong. Caveat programmer.