Haskell utilities

[pozorvlak]

I still haven't fixed the bug in my Siteswap program. But while writing it, I noticed a few utility functions I'd have liked, which don't seem to be provided. So I tried to write them, and ran into some problems.

Zerothly, the Sieve of Eratosthenes. Probably not very generally useful, but it's a nice algorithm:

-- Sieve of Eratosthenes
-- eg primes = sieve (\x y -> (y `mod` x /= 0)) [2 .. ]
sieve f []      = []
sieve f (x:xs)  = x:filter (f x) (sieve f xs)

And yes, I know that's not quite the algorithm as usually used (I'm testing the remaining values using a function rather than having a list of truth values and just turning off every n'th one), but it was what I needed.

Firstly, the notIn function. I want to check that something is not an element of a given list. So not.elem, right? No. Because elem has type a->[a]->Bool, so to be composable with elem a function must have type ([a]->Bool)->b. This is not very useful. So we need a function

cmp2 :: (c->d)->(a->b->c)->(a->b->d)
cmp2 f g x y = f $ g x y

Now notIn = cmp2 not elem. That was easy. I'm somewhat surprised cmp2 isn't a standard library function, but I can't find anything relevant-looking with Hoogle. Of course, this is just one case of a more general problem: we could define

cmp3 f g x y z = f $ g x y z
cmp4 f g x y z w = f $ g x y z w
...

But this is all rather messy: it would be nice to define cmpN once and for all. But I can't see how to do this, for reasons I want to get into below.

Secondly, I found a need for the outer product of two lists (ie, the matrix of all possible pairs, or in this case, the result of applying a binary function f to every pair of elements from xs and ys). This is built-in to APL, and so I think I'm right in saying that it's a useful general pattern, but it doesn't seem to be part of the API. It's easy enough to write:

outer :: (a->b->c)->[a]->[b]->[[c]]
outer _ [] _      = []
outer _ _ []      = []
outer f (x:xs) ys = map (f x) ys:outer f xs ys

But this is an instance of a more general construct. It's a bit tricky, but we can also define a version for 3-argument functions:

outer3 _ _  _  [] = []
outer3 f xs ys zs = map (flip (outer ($)) zs) (outer f xs ys)

Or 4-argument functions:

outer4 _ _  _  _  [] = []
outer4 f xs ys zs ws = map (map (flip (outer ($)) ws)) (outer3 f xs ys zs)

OK, a pattern is starting to emerge. It should now be possible to write a function outerN which takes an integer argument, an n-ary function, and n lists, and gives their n-dimensional outer product, right? Er, no. The trouble seems to be that the arguments come in the wrong order - note that outer4 uses only ws itself, and hands the others off to the recursive call. If you could somehow reverse the order of the next n arguments, you could define outerN n as {stuff} `cmpN (n-1)` (outerN (n-1)) and let partial evaluation handle it. But I haven't been able to do this. Every time I get close, I get a type error (on the upside, type errors don't make my eyes glaze quite as much as they used to).

So, am I just being stupid? Is it possible to write these functions in Haskell? Or do we need to use a macro system? The existence of zip3, zip4, etc, suggests that it's not just me...

Another problem that the above threw up is the need for a pretty-printer à la Data::Dumper. I see that SPJ has written one, but I was away from the 'net when I was doing this, and I wanted to have a bash at writing one myself. Here was my attempt:

-- pretty printer?
-- have a typeclass PrettyPrintable, or use newtype and redeclare show?
class (Show a) => PPrint a where
        pprint :: a -> String
        pprint = show

instance (PPrint a) => PPrint [a] where
        pprint xs = "[\n  " ++ (concat $ intersperse (",\n  ") $ map pprint xs) ++"\n]"

--instance (Show a) => PPrint a where
--      pprint = show

instance PPrint Integer where pprint = show
instance PPrint Char where pprint = show

It didn't work. Calling pprint 3 gives

ERROR - Unresolved overloading
*** Type       : (Num a, PPrint a) => [Char]
*** Expression : pprint 3

, and the commented-out bit just doesn't compile. Waaah. What am I doing wrong, anyone?

Comments

[totherme.livejournal.com]

weird if you're thinking in Haskell, but completely standard practice in APL or J :-)

Can you give me a reference? Everything I know about APL and J, I know from reading the relevant 2 wikipedia pages just now (so, almost nothing ^_^). The APL page gives an example which makes use of the in-built outer product operation - but that looks to me to just be outer2 - not weird at all, and of type

(a->b->c)->[a]->[b]->[[c]]

...

[pozorvlak.livejournal.com]

OK, I've never used either language, and don't have interpreters to hand. So I could be wrong, and anyway, I was talking more about the approach to programming rather than the actual APL outer product operation. But my understanding is that the outer product in APL despatches at run-time on the dimensions of its argument, so if R is an n1*...*nj array and S is an m1*...*mk array, then o.x R S is an n1*...*nj*m1*...*mk array. I don't know if there's a version of outer product which takes a functional argument, but I expect so (and almost certainly in J, which is apparently influenced heavily by functional languages).

There's an excellent explanation of an APL program on this page (http://www.chilton.com/~jimw/setgame.html) - I found it pretty mindblowing when I first read it. I want to learn APL/J at some point for the same reason that I want to learn Haskell better - to expand my mind, and give me new ways of thinking about programming. Though they're using the word "monad" to mean "unary function", which I'm afraid I can't support :-)