January 2018

S M T W T F S
  123456
78910111213
14151617181920
21222324252627
28293031   

Style Credit

Expand Cut Tags

No cut tags
Monday, October 23rd, 2006 07:10 pm
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?
Friday, October 27th, 2006 02:38 pm (UTC)
Ok yes - you don't return a flat list do you... In fact, we have:
outer :: (a->b->c)->[a]->[b]->[[c]]
outer3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [[[d]]]
outer4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [[[[e]]]]
outerN :: (t0 -> .. -> tn) -> [t0] -> ... -> [t(n-1)] -> ([*n)tn(]*n)


So, it seems that there are three challenges:

  1. The variable number of arguments to f

  2. The variable number of arguments to outerN (the n list args)

  3. The variable depth of nesting in the return result



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:

putStrLn $ head $ last $ outerN (++) ["foo", "bar"] ["grue", "blort"]


..but as soon as I change the input to the function:

outerN (\x y z -> x++y++z) ["foo", "bar"] ["grue", "blort"] ["fish", "radiator"]


...I also have to change how I manage the output:

putStrLn $ head $ last $ concat $ outerN (\x y z -> x++y++z) ["foo", "bar"] ["grue", "blort"] ["fish", "radiator"]


...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:
> outer1 :: (a -> b) -> [a] -> [b]
> outer1 = map

> outer2 :: (a->b->c)->[a]->[b]->[[c]]
> outer2 f xs ys = map g xs
>     where g x = map (f x) ys

> outer3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [[[d]]]
> outer3 f xs ys zs = map g xs
>     where g x = map (h x) ys
>           h x y = map (f x y) zs

> outer4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [[[[e]]]]
> outer4 f ws xs ys zs = map g ws
>     where g x = map (h x) xs
>           h x y = map (i x y) ys
>           i x y z = map (f x y z) zs


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 ;)
Friday, October 27th, 2006 03:11 pm (UTC)
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 :)
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 :-)
Friday, October 27th, 2006 04:09 pm (UTC)

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]]
...
Saturday, October 28th, 2006 04:37 pm (UTC)
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 :-)