fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

Haskell’s standard State monad types allow the programmer to define a computation that works with some state in a way that looks and feels similar to using mutable state in an imperative language. However these State monad types are limited in that the type of the state cannot change during the computation.

Normally this is fine, but what if we really wanted to use the mechanics of a state monad to pass some state value that changed type, e.g. some mutually-recursive tree structure we would like to traverse?:

» read more…

I’ve been collaborating with Gabor Greif on a new version of his ‘thrist’ module, which was just released last night! I approached Gabor with some new ideas that came to me as I was writing a module that uses Thrists heavily, and he invited me to co-author this version. (See below for a brief explanation of Thrists).

I noticed that in the previous version, the function foldThrist was essentially a foldr with a type signature that was overly restrictive.

For instance, one could not define an identity function on Thrists in terms of the foldThrist function, the way one can with regular lists, e.g.:

foldr (:) [] [1..4] == [1,2,3,4]

Other additions followed as I tried to define the Thrist equivalent of many useful list functions. For example I wanted to define a foldl-like function that we could use to reverse a Thrist.

Check out the release announcement on Gabor’s blog, along with his draft paper on Thrists.

» read more…

Like the Lambda Calculus (on which Lisp is based), Combinatory Logic is a formal system that can be used to model and study computation. What makes it fascinating is that it is as powerful as the (already simple) lambda calculus, but has no need for the variables that LC requires to perform substitution!

Here I show how we can use Haskell’s type classes and other language features to model the Combinator Calculus. The goals of this module were:

1. don’t force any one evaluation strategy
2. allow users to define new combinators without exposing the implementation
3. allow new combinators to be defined in terms of other already-defined combinators.
4. discourage creation of non-sensical combinator expressions, or possible mis-use of the module
5. hide existential types and anything else exotic

If you want to play with it, you can do a:

$> darcs get http://coder.bsimmons.name/code/CombinatorCalculus

» read more…