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]

Having found out about the magic compiler switches above, I tried the following experiment:

> class Pretty a where prettyPrint :: a -> String

> instance Show a => Pretty a where 
>     prettyPrint = show

> instance Pretty a => Show a where
>     show = prettyPrint

$ ghci -fallow-overlapping-instances -fallow-undecidable-instances -fallow-incoherent-instances tmp.lhs

*Main> 5
5
*Main> prettyPrint 5
"5"
*Main> show 5
"5"
*Main>

So, I guess it probably is, at least in some sense, "solved" ;)

[totherme.livejournal.com]

Incidentally, the thing I linked to, explaining why this isn't allowed: That was "YAHT" - "Yet Another Haskell Tutorial", and was based on Haskell98 - the old standard we both played with many years ago. There's been no official change in the language spec since then, but lots of cool stuff has been done by various folk. The ghci switches I gave you are glasgow ones - if you start doing this, you're programming in glasgow extensions, not "Haskell" as such.

I think this is ok - since that's how things evolve. Most of these sorts of extensions will end up as the new standard in Haskell'.