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]

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

I can think of two ways around this. First, a lambda:

\x -> not.elem x

...which isn't bad, but it's not point free which irks me. Whenever one has irksome pointed code, the thing to do is to ask the lambdabot:

@pl \x -> not . elem x
(not .) . elem

...which also isn't bad, but I don't think it's as readable as all that, really.

So, let's try a different tack. The problem is composing a function that takes many arguments, so let's make it take only one argument:

uncurry elem

Now, we can compose it with the not, like we wanted:

not . uncurry elem

...and then restore the original number of arguments:

curry $ not . uncurry elem

Check that it works (because I'm still a slightly paranoid coder, and like to see things working):

Prelude> let gds = curry $ not . uncurry elem
Prelude> 1 `gds` [1,2,3,4]
False
Prelude> 1 `gds` [2,3,4]
True
Prelude>

That's the most readable solution I can think of atm :)

[totherme.livejournal.com]

Oh - this also gives us the general case of your cmp2, cmp3, etc:

Prelude> let gds2 f g = curry $ f . uncurry g
Prelude> let gds3 = not `gds2` elem
Prelude> gds3 1 [1,2,3,4]
False
Prelude> gds3 1 [2,3,4]
True

And point free:

 @pl \f g -> curry $ f . uncurry g 
 (curry .) . (. uncurry) . (.)

In this case, I think I prefer the pointed version. I'm sure there are those that would disagree ;)

[totherme.livejournal.com]

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

No, the problem is that you can't have a function with a variable number of arguments in a language that has partial function application. For example, I can define:

sum4things a b c d = a + b + c + d

and, I can apply it partially:

sum2thingsPlusSomeMoreStuff = sum4things 4 9

which gives us a function that adds (4+9) to its two arguments. This is a handy technique, used to do things like increment = map (+1) but it does mean that I can never have a function sumNthings a b ... z = a + b + ... + z because how would I know that I'd given it enough arguments to finally return its result?

If we want to operate on arbitrary numbers of things, we use lists explicitly... That being the case, the type of your outerN might be something like:

outerN :: SomeFunc -> [[a]] -> [[a]]

And that loses some generality of the lists, but that's not the pressing issue. The pressing issue is defining the type of SomeFunc... Since you can't specify the type of an Nary function in a language with partial application.

I was looking at that, trying to think of a way around it, when I noticed that in your definition, outer4 f makes a call to outer3 f, which makes a call to outer f. Now, I can't think how that would work if f is supposed to have a different arity in each of those contexts.

If it is ok for f to just take 2 arguments, then the type of the function you want is probably:

outerN :: (a -> a -> a) -> [[a]] -> [[a]]

Which we might be able to define as something like:

outerN f (x:y:[]) = outer f x y
outerN f (x:y:z:zs) = map (flip (outer ($)) x) (outerN f (y:z:zs))
outerN _ _ = error "Too few items in the list"

...but I don't think that's a programme that does what you want. I think there are deeper bugs than that :)

It's true that the necessity of zip3, zip4, etc, does indicate a weak spot in the language. I don't think I've yet come across an occasion where I've genuinely been caused trouble by it though. I've used liftM2 once, which was great. A couple of times I've thought I needed nary tuples (for some n that's constant over several tuples, and a particular call to a function), but discovered on inspection that what I had was a data structure that was more fundamentally broken elsewhere. I've not yet had to resort to template haskell, but I believe that'd be the way to solve it if I really had to.

[michiexile]

The implementations of permutations that I brought recently is one point where the lack of being able to parametrize things really does make for worse code.

In the ideal case, I would want to be able to write a type, parametrized by the integers, and where once the parameter was fixed (i.e. once the type is -used-), everything matches up using this parameter. As it is now, I parametrize what should be a 0-ary function: the group identity, since there is no other decent way to figure out what it should be.

Or, as an alternative, I could always work in the infinite symmetric group, viewed as a limit (colimit? I can never tell them apart) of the finite symmetric groups...

[totherme.livejournal.com]

Ok, it took a night's sleep, and a kick from michiexile mentioning the word "parametrize" to drag the reference out of my memory, but I'm finally reminded of generics. I think I may have seen them mentioned in #haskell, and I've certainly seen lambdabot patches about supporting them.

That page contains a link to a paper entitled "Scrap more boilerplate: reflection, zips, and generalised casts". Quoting the abstract:

We also show how to perform generic ``zips'', which at first appear to be somewhat tricky in our framework.

I've not yet read the paper, so I could be barking up entirely the wrong tree, but I guess it's pretty clear that it should go on my reading list ;)

Apparently the latest ghc supports all this stuff out of the box.

[michiexile]

OOOOOOOH? It does!?!? Tell me how!!

[totherme.livejournal.com]

import Data.Generics I think... Disclaimer though: I've not yet read any of that documentation (aside from the abstract) or experimented with any of those libs - they may well not do what I think they do :)

[pozorvlak.livejournal.com]

Woo, funky! Reading now...

BTW, "Generics" is the Ada term for templates, and they can be used to do this sort of thing, in much the way that michiexile mentions above (as can C++ templates, of course...)

[elvum.livejournal.com]

Java term too, although gds tells me they are almost but not quite entirely unlike the Haskell concept with the same name. I don't pretend to know things about Haskell yet though.

[totherme.livejournal.com]

There's my evil twin again... ;)

[pozorvlak.livejournal.com]

From what I can see, Java has borrowed a lot from Ada (though for political reasons, they may not acknowledge this). Some features, but mostly the design mindset. Consider: both are strongly-typed (bondage-and-discipline, even) languages, with large standard libraries, touted as good for embedded programming, exception handling, memory management and run-time checking, and with heavy emphases on separate development of isolated software components, compile-time correctness checks, and concurrency.

I mentioned this thought to totherme once, and he said "Ada isn't object-oriented (or at least wasn't until 1995), and that's a major feature of Java". True, but in 1977 object-oriented languages were still research tools, so I don't think you can blame them for that :-)

Java/Ada generics when parametrized by types aren't needed in Haskell (or rather, they're an inherent feature of the type system) because you can have types containing type variables. For instance, [a] is the type "list of things of type a", which you'd need a generic for in Java/Ada. On the other hand, there's no possibility in vanilla Haskell of parametrizing types by things which aren't other types - you can't have a type SymmetricGroup 3 for instance. This is what you need Haskell generics (or Template Haskell) for. There's more detail in this Wikipedia article (http://en.wikipedia.org/wiki/Generic_programming).
[Incidentally, I'm pleased to note that both Java and Ada have only single instances of a given generic, and so avoid C++-style code bloat]

[pozorvlak.livejournal.com]

Colimit. It depends on the morphisms, of course :-) S_oo is the colimit of the diagram

S_1 -> S_2 -> S_3 -> ...

where the arrows are the maps induced by the injections {1..n} -> {1..n+1} taking 1 to 1, 2 to 2 etc.

In general, colimits are disjoint unions/free products and quotient-type things, and limits are products and subobjecty-things. Colimits are generally harder to compute.

Permutation code: have you tried using the Reader monad? See here (http://haskell.org/haskellwiki/Roll_your_own_IRC_bot) for the technique.

[pozorvlak.livejournal.com]

I was looking at that, trying to think of a way around it, when I noticed that in your definition, outer4 f makes a call to outer3 f, which makes a call to outer f. Now, I can't think how that would work if f is supposed to have a different arity in each of those contexts.

Not sure I get you - the whole reason it works is because of partial evaluation. f has arity 3 (and returns a function) when called with outer3, and arity 4 (and returns a value) when called with outer4. I was hoping to achieve the same effect more generally in a definition of outerN.

Ah well. I'll have a look at the generics stuff, and if not it's time to learn Template Haskell at last :-)

[totherme.livejournal.com]

Oh, I see... Sorry - misunderstood your spec.

Ok, in which case:

outer f xs ys = [f x y | x <- xs , y <- ys ]
outer3 f xs ys zs = [f x y z | x <- xs, y <- ys, z <- zs]
outer4 f ws xs ys zx = [f w x y z | w <- ws, x <- xs , y <- ys , z <- zs]

...which is pretty succinct and elegant. We still don't have a generic outerN, but we do have quite a nice way of writing any call we're likely to make to it (so long as we know N at compile time). If you want tuples btw, you don't need to define a special f, you can just write

[(x,y) | x <- xs , y <- ys]

So, if we know n at compile time, then it starts to look as if outerN f as bs .. zs could fairly simply become syntactic sugar for the full list comprehension. If you want. The lambdabot has a module called BotPP, which is a haskell pre-processor written in haskell to do the boilerplate for talking to IRC. I guess if you were using a lot of outerN style list comprehensions, you might find it worth while to define yourself a syntactic sugar like that. And maybe generics has the answer - I still haven't read it yet.

We still don't have a run time dynamic thing that can take any Nary function. I'm starting to wonder if the type guarantees we've come to expect from haskell (no side effects outside IO, etc) would be decidable if you could do that... Having said that, I know that there's a well defined corner case of the GHC extensions to the haskell type system which is undecidable (and which some enterprising chap used to implement a type-level lambda calculus, just to prove a point), so it still might be possible...

Sleep :)

[pozorvlak.livejournal.com]

Aha, I didn't think of using list comprehensions. That's not quite the function I was thinking of , because it flattens everything into one list. Of course, that would be fine in the case I actually needed, because I concatted the output of outer as soon as I generated it.

[totherme.livejournal.com]

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 ;)

[pozorvlak.livejournal.com]

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 :-)

[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 :-)

[totherme.livejournal.com]

The pretty printer:

Finally got around to trying to figure this bit out. The main problem you're having is that

class (Show a) => PPrint a

doesn't do what you think it does.

What you want is that all things of type Show are also of type PPrint (and you might choose to PPrint some other things later too, but at least you want this default) - and your mathematician's brain uses the implication symbol to represent that wish, so you get the above snippet. In haskell, though - this means that PPrint is a subclass of the type Class Show. That is to say that every type a which has an instance PPrint a, must also have an instance Show a. From the point of view you're thinking from, the implication actually goes the wrong way :)

I think having the arrow the way round it is is entirely justifiable, from another point of view. But that's another post.

For the moment, it's just important to realise that

class (Show a) => PPrint a

means that there's a new class called PPrint, and when I choose to make something an instance of it, I'll be able to use the Show method in my instance declaration. It doesn't automatically make Showable thing PPrintable things. To demonstrate what it does do, we can have:

> class Show a => Pretty a where 
>     prettyPrint :: a -> String
>     prettyPrint _ = "words"

> instance Pretty Int

Main> prettyPrint 2
ERROR - Unresolved overloading
*** Type       : (Num a, Pretty a) => [Char]
*** Expression : prettyPrint 2

Main> prettyPrint (2 :: Int)
"words"
Main> 

So, the error you were getting was because you hadn't declared the thing you were trying to print as an instance of the class you wanted to print with. In my example that's because '2' has a generic type of Num, unless I force it into Int (which was an instance of Pretty).

So, hopefully that clears up the errors you were getting, and why you were getting them :)

What you actually wanted to write was:

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

Unfortunately, that results in:

Main> :load "/homes/gds/tmp.lhs"
ERROR "/homes/gds/tmp.lhs":10 - Syntax error in instance head (constructor expected)
Hugs.Base> 

There's a good reason for that, honest :) It's described here. Scroll down to the bit about

instance Eq a => MyEq a where
    myeq = (==)

Off the top of my head, I can't think of an obvious way to do precisely what you want - but a part of that is that I've just been distracted by the information on "Kind"s which follows that bit I just linked to ;)

If SPJ's done it, it must be possible. I'll take a look at his thing at some point, I guess :)

[pozorvlak.livejournal.com]

It turns out that SPJ's library isn't a Data::Dumper equivalent: it's more of a text-wrapper type thing, fmt/pr/fold (http://www.gnu.org/software/coreutils/manual/html_mono/coreutils.html#Formatting-file-contents)-style.

My current thoughts on the matter is that it might be possible to use Template Haskell to generate a pprint function from the show function for a class, adding an extra level of indentation whenever show calls itself recursively. Not sure if that would work, but it sounds worth a go. But still, compare to the simplicity of the Perl version :-(

[totherme.livejournal.com]

More playing, and a quick request from #haskell later, and we have:

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

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

> instance Show a => Pretty [a] where
>     prettyPrint [] = "nil"
>     prettyPrint (x:[]) = prettyPrint x
>     prettyPrint (x:xs) = (prettyPrint x) ++ "\n" ++ (prettyPrint xs)

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

*Main> putStrLn $ prettyPrint 5
5
*Main> putStrLn $ prettyPrint [5,6,7,8]
5
6
7
8
*Main>

I like the idea of asking the compiler's permission to be incoherent :)

[pozorvlak.livejournal.com]

There's a good reason for that, honest :)
Hrm. You're the compsci, but surely it's possible to detect loops in a graph? In which case, the compiler could bitch iff the loop it describes occurs, and not otherwise?

[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'.