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:
Firstly, the
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:
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:
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 functioncmp2 :: (c->d)->(a->b->c)->(a->b->d) cmp2 f g x y = f $ g x yNow 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 ysBut 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 = showIt 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?
Tags:
no subject
So, it seems that there are three challenges:
These are all things that we need to understand if we're to use this function in code. Even dynamically typed code - since that code will have a type when it's run - and if it's not used consistently, it'll crash.... So if we had a dynamically typed haskell, and an implementation of outerN, the following would be legal:
..but as soon as I change the input to the function:
...I also have to change how I manage the output:
...so, it's a function I think would be particularly challenging to programme with, if no way could be found to statically type check it.
We can deal with challenge 2 (statically) by using a list. That's easy. 1 and 3 are the tricky ones...
I was vaguely thinking about attacking 1 by taking a function from tuples to tuples, and using the corry and uncurry function to partially evaluate it as at each level. That's not going to work though, firstly because curry's not general - it only works with pairs, not tuples - and secondly because we have to specify the order of our tuples to the type system too :)
3 is the hardest, I reckon. This is a function which could return an arbitrarily nested list. That's pretty weird.
The only line of thought I have any hope for at the moment, in terms of producing a useful outerN, is the notion that we might need something that's a generalisation of a list. This line of thought is inspired by the observation that outer1 = map. This is something I noticed when re-writing outer[2..4] to get a better idea of what they actually were:
It seems to me that outer could be considered to be a multi-dimensional generalisation of map. If that's the case, then perhaps some kind of square multi-dimensional generalisation of a list is in order :)
I'll have a think, and get back to you ;)
no subject
Yes, exactly.
As for your problems 1-3, they're all weird if you're thinking in Haskell, but completely standard practice in APL or J :-)
no subject
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 ...
no subject
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 :-)