4/09/2010
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:
- don’t force any one evaluation strategy
- allow users to define new combinators without exposing the implementation
- allow new combinators to be defined in terms of other already-defined combinators.
- discourage creation of non-sensical combinator expressions, or possible mis-use of the module
- 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 the rest of this article »
24/03/2010
We don’t usually give much thought to Numeric data types beyond whether we want to work with integers or decimal numbers. And that is a shame! In this post I’ll look at how we can actually do arithmetic operations lazily, and in the process hopefully reveal a bit about haskell’s numeric classes.
module LazyArithmetic
where
We will be using Lennart Augustsson’s numbers library which can be installed from hackage with cabal-install:
$> cabal install numbers
import Data.Number.Natural
import Data.List(genericLength)
Consider two functions: the Prelude function sum and genericLength from the List library:
genericLength :: (Num i) => [b] -> i
sum :: (Num a) => [a] -> a
…two simple functions that have the potential to be very expensive, depending on the length of the list and the values of the elements.
Read the rest of this article »
10/02/2010
The function groupBy from haskell’s standard library is defined in terms of span, the effect being that the supplied predicate function is used to compare the first element of a group with successive elements.
This isn’t clear from the docs, and you might try to do this and wonder at the output you got:
*Main> groupBy (< =) [3,4,5,3,2,1,4,4,1,1,2,3,4,5,4,5,6,7]
[[3,4,5,3],[2],[1,4,4,1,1,2,3,4,5,4,5,6,7]]
Read the rest of this article »