Sunday, December 17, 2006

Questions on Haskell Style (and Polynomials redux)

Someone posted, on the Haskell "Blow your Mind" page, a much more concise implementation of Polynomials as Numbers than I managed to come up with. There are a couple things I learned by comparing it with my version:

  • Use of zipWith (+) instead of map (\v -> (fst v + snd v)) zip; obviously I need to get to know the libraries better
  • zipWith' is introduced to zipWith two lists together, padding the shortest one with zeroes. Jeremy Gibbons suggested the same thing, calling it longzipwith, and this is parallel to what I did without the "with" in my zipLong function.
  • They had the same questions I did about what to do with the required signum and abs functions. Mikael suggested in a comment that I should use the NumericPrelude library instead of the standard one, for a more sensible generic definition of a number.
  • Jeremy and Blow-your-mind both used one less line in their zip function definition than I did: they manage to define it without explicitly handling the case where both lists are null.
And here are some questions I have -- please comment if you have any ideas!
  • The Blow-your-mind version uses [a] instead of Poly [a] as its polynomial type. My feeling is that an explicit constructor and data type like Poly is better, because a polynomial is not the most obvious way to interpret a list of numbers. However, my functions ended up being a lot wordier, pulling that constructor on and off the list all the time. What's the better style choice here?
  • The multiplication function has me scratching my head. It seems terser, but less communicative to me. If you're got more experience with functional programming than I do: is the Blow-your-mind version much more clear or efficient, and is it worth it? Is mine only clearer to me because I'm not used to FP style yet? Or maybe tight APL-like gnomishness is part of the point of the Blow-your-mind page. (Here they are again if you don't want to follow all the links).
My version:
> scalarPolyMult :: (Floating a) => a -> Poly a -> Poly a
> scalarPolyMult c (Poly rs) = Poly $ map (*c) rs

> multByUnknown (Poly rs) = Poly (0:rs)

> multPoly :: (Floating a) => (Poly a) -> (Poly a) -> (Poly a)
> multPoly (Poly []) cs = Poly []
> multPoly (Poly (b:bs)) cs =
> addPoly
> (scalarPolyMult b cs)
> (multPoly (Poly bs) (multByUnknown cs))
Blow-your-mind version:
  xs * ys = foldl1 (+) (padZeros partialProducts)
partialProducts = map (\x -> [x*y | y <- ys]) xs
padZeros = map (\(z,zs) -> replicate z 0 ++ zs) . (zip [0..])

Wednesday, December 13, 2006

Automatic Spaghetti Refactoring

I wonder under what conditions it would be possible to take a working body of spaghetti code and automatically refactor it to pull out all references to one specific resource, or some other definable subset of the program's activity. Afterwards, your code would be as bad as before, or worse, in terms of organization, but it would at least be semantically equivalent.

If you could do this quickly, on demand, you could present the object to a programmer in some kind of constrained editor for modification, then re-inline the changes back into the original structure of the code. This would let a programmer pretend a design was nicely modular and object-oriented for the sake of conceptual simplicity in making a change, but without requiring the code to actually be organized at all.

Why bother doing this? It could be that the code is already organized according to some orthogonal concern that you don't want to mess up; or it's truly messy spaghetti code that you don't understand; or maybe more interestingly, it's represented internally as a dataflow graph or something, where there may be no linear or hierarchical structure to it by nature.

I know refactoring gets done piecemeal by menu options in some IDE's, and I know something similar is done within compilers as optimization steps, for example inlining, and loop unrolling, but I haven't heard of large scale, temporary changes just for the purposes of presentation.

The idea of making a transformation, applying a change, then reversing the transformation, puts me in mind of the notion of "conjugation" from group theory. However I haven't gotten to that chapter yet in my Algebra book, so I don't really know if there are any monkeys in that tree.

Thursday, December 07, 2006

Awkward db2 SQL syntax

I'm continually frustrated by the awkwardness of SQL syntax in DB2 (I do database work on an IBM iSeries). You can't do an update on a joined table; you can only update one table, so you have to do a subselect, typically expressing exactly the same subselect in two places in the same query. See Brett Kaiser's helpful example. I keep shying away from doing them this way because it seems so wrong, but I keep coming back to it as my best alternative. A language should not make you say the same complicated thing twice in once sentence. Anaphora is your friend, IBM!

Tuesday, December 05, 2006

Simonyi on Comments in Algol-60

Check out this fascinating slideshow by Charles Simonyi about how the language Algol-60 was originally used in practice -- as a language for comments. He observes that good code comments can be a good source of ideas for new programming language constructs, since comments are where programmers express ideas that they feel can't currently be made clear or concise in the code itself.

Monday, December 04, 2006

The Zen of Referential Transparency

Here's another interesting connection between Buddhist philosophy and math: this blog post by metaperl draws a connection between Haskell's lack of state variables, and Eckhard Tolle's belief that "the only thing that is real is the present moment."

I'm not familiar with Tolle, but this is a part of Zen thinking as well. You could choose to look at the past and future only as memories and projections that exist now, rather than as independent realities. I'm not claiming to know something that arcane about the universe. But it makes sense, using category theory as a metaphor, that you could choose to view the past and present and future as three real objects; or you could choose to look at the currently existing traces of the past, and currently existing precursors of the future as categorical arrows, and merely define the past and future in terms of those.

A pure function will return the same value every time it is called with the same arguments; this is convenient because it makes them timeless in a sense. If you define some function

f(x) = x+4,

you can say that f(2) = 6; and it's always true. If f(2) gets called 10 times during a program's execution, you only have to really do the addition once; after that you know it as a timeless fact. Even calculating it the once is bending to necessity; after all, it was already true before we calculated it.

But if we have some other function, g(), and we pass the result of f into it

g(x) = x * 7
print g(f(2))

Well, g(6) = 42 no matter what, and g(f(2)) = 42 no matter what. They're both universal timeless facts about this little system. But in practice the computer has to calculate f(2) in order to know what to feed to g, so that g(f()) relationship works like time. f is "before" g, even though they're both mathematically fixed, static, and unchanging.

My feeble understanding of Zen is that one can learn, among other things, to experience time as an artificial construct of this sort, and not as something fundamental. It's a pretty hard to nail down what's concretely different in this perspective, though, because it's probably isomorphic to the more conventional view of time as a mighty river, but supposedly there is a psychospiritual benefit to changing one's perspective in this way.

Some links:
An article about Zen, Time, and Bohm's interpretation of quantum physics
A prior post of mine on dependent origination and category theory

Sunday, December 03, 2006

Moving to new URL


I'm moving to Please update your feed! I was doing an FTP upload from to my ISP, but the comments never worked, and it just doesn't seem worth the trouble to do it that way.

Polynomials as numbers

So, I was trying to learn category theory, having gathered it was a good thing to know for people interested in programming language theory. I kind of got bogged down though -- it's castles built on castles built on castles in the air, and I was losing track of reality in all the abstractions. My book would talk about a category of Groups, for example, so I'd go looking up Groups in my faithful Wikipedia. I'd get the concept, it's not that tricky in itself, but obviously understanding the definition of a group does not make one a group theorist.

So, I finally declared "mission accomplished" brought the troops home to a ticker-tape parade, and started in on a group theory textbook instead (Knapp's Basic Algebra). I'm enjoying it a lot more -- it starts up where I left off with math classes, so I don't feel like I'm a freshman in a senior-level class.

Anyway, this book starts with a kind of review of polynomials, simultaneous equations, matrices, vector spaces, etc. that is stuff I've seen before, but with a more theoretical spin, that either was missing from my high school algebra or I've simply forgotten it. The book points out that factoring integers into products of smaller integers, is very much like factoring polynomials into products of polynomials of smaller degree, and a prime number is like a polynomial you can't factor any further (like say x2+9 = 0, when you're dealing with Reals). Of course you can also add, subtract, multiply, and divide polynomials, and the result is always still a polynomial. If a topologist can't tell a coffee cup from a doughnut, then a group theorist can't tell a polynomial from an integer.

Well, maybe she can; obviously integers and polynomials have some different properties. But I'm tickled enough with the idea that a polynomial is a kind of number, that I created a polynomial instance of Num in Literate Haskell as an exercise, reproduced below for your edification.

Since I'm also still learning Haskell, I welcome any critiques you might have of my code. I like the fact that the data structure I used (just a list of coefficients) turned out to make for short code; but it doesn't come out very readable. The fact that prepending a 0 to a list multiplies the polynomial by X seems as cryptic as it is convenient.

> module Main where
> main = print testP

I represent a polynomial as a list of its coefficients,
with the constant first, then the X, the X^2, etc. So
3x^2 - 4 would be Poly [-4,0,3].

> data Floating a => Poly a = Poly [a] deriving (Eq)

Now we evaluate by filling in the unknown. Note that
ax2 + bx + c evaluated at x is the same as
(ax + b)x + c, so you can evaluate it by taking the constant
term, popping it off the list, then multiplying x by the
polynomial interpretation of the rest of the list.

> evalPoly :: (Floating a) => (Poly a) -> a -> a
> evalPoly (Poly []) x = 0
> evalPoly (Poly (c:cs)) x = c + x*(evalPoly (Poly cs) x)

To add two polynomials, add corresponding coefficients. If
one is shorter than the other, you want to use zeroes. I don't
know how to do this beautifully with standard functions, because
zip cuts off when the shortest list runs out. So I defined
a helper function zipLong, that keeps going till the longest
list is done, filling in a default value.

10 Points to whoever emails me with a shorter, cleaner,
idiomatic way to do this.

> addPoly :: (Floating a) => (Poly a) -> (Poly a) -> (Poly a)
> addPoly (Poly r) (Poly s) = Poly $ map (\v -> (fst v + snd v)) (zipLong r s 0)

> zipLong [] [] d = []
> zipLong (x:xs) [] d = (x,d):(zipLong xs [] d)
> zipLong [] (y:ys) d = (d,y):(zipLong [] ys d)
> zipLong (x:xs) (y:ys) d = (x,y):(zipLong xs ys d)

Multiply a polynomial by a scalar. I have a feeling this
could be defined somehow under an instance of Num so that
the * operator is automatically overloaded. Not sure how.

> scalarPolyMult :: (Floating a) => a -> Poly a -> Poly a
> scalarPolyMult c (Poly rs) = Poly $ map (*c) rs

Since (ax^2 + bx + c)x = ax^3 + bx^2 + cx,
then Poly [c b a] * x = Poly [0 c b a]

> multByUnknown (Poly rs) = Poly (0:rs)

To multiply two polynomials, P1 * P2, where P2 = (dx^2 + ex + f),
rewrite as f*P1 + P1*x*(dx + e); the first term is a scalar multiplication
and the second has one less degree, so we can recurse on it. The
(Poly bs) term below is (dx + e) in this example.

> multPoly :: (Floating a) => (Poly a) -> (Poly a) -> (Poly a)
> multPoly (Poly []) cs = Poly []
> multPoly (Poly (b:bs)) cs =
> addPoly
> (scalarPolyMult b cs)
> (multPoly (Poly bs) (multByUnknown cs))

Define a polynomial as a number. I'm cheating a little by
picking a dumb definition of signum; really a polynomial
with an unknown isn't positive or negative before a number
is plugged into it, so I'm just defining it as the sign of
the constant term.

> instance (Floating a) => Num (Poly a) where
> s + t = addPoly s t
> negate (Poly cs) = Poly $ map (\q -> -q) cs
> s * t = multPoly s t
> abs s
> | signum s == -1 = negate s
> | signum s /= -1 = s
> signum (Poly []) = Poly []
> signum (Poly (c:cs)) = Poly [signum c]
> fromInteger i = Poly [fromInteger i]

And define a cheesy way to print out a polynomial

> instance Floating a => Show (Poly a) where
> show (Poly []) = "null"
> show (Poly cs) = concatMap
> (\c -> " + " ++ (show (fst c)) ++ "X^" ++ (show (snd c)))
> (reverse (zip cs [0..length(cs)-1] ))

Define some examples and some tests.

> p = Poly [2,0,1,2] -- 2x^3 + x + 2
> q = Poly [0,0,0,3,4] -- 4x^4 + 3x^3

> testP = (p * q == Poly [0,0,0,6,8,3,10,8]) &&
> (p + q == Poly [2,0,1,5,4]) &&
> (evalPoly p 3 == 65.0 ) &&
> (3 * p == Poly [6,0,3,6]) &&
> (show p == " + 2.0X^3 + 1.0X^2 + 0.0X^1 + 2.0X^0")