Log in

No account? Create an account
Luke's Weblog [entries|archive|friends|userinfo]
Luke Gorrie

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Strange company [Apr. 17th, 2007|08:48 pm]
Luke Gorrie
[Tags|, ]

I had fun unicycling around Stockholm with the illustrious Haskell hacker Shae Erisson on the weekend. It was really interesting to spend some hours talking about programming and computer science with a proper Haskell guy and I was relieved that we disagreed about almost everything. :-)

I was also excited to discover that other people actually do tricks on unicycles!

He did succeed in reminding me why Haskell matters: it's because Haskell people can rewrite any one of your programs in half as much code. They're the masters of expression.

For a relevant example I could see that the very simple Liskell example at ILC:

(define (fact n)              
  (if (= n 0)
      (* n (fact (- n 1)))))
which was shown transposed into Haskell as roughly:
fact n =
  if n = 0
    then 1
    else n * (fact n-1)
would be shorter even in Erlang-accented Haskell:
fact 0 = 1
fact n = n * (fact n-1)
and suspected it would be a one-liner to a true Haskellite, which turns out to be so:
fact n = product [1..n]
.. not that I think Clemens meant for factorial to be the knockout punch of course, but I found the example provocative. :-)

So thanks for popping by Shae!


From: (Anonymous)
2007-04-17 08:33 pm (UTC)


Prolog is sometimes rather more concise than Haskell - consider coding the legal moves for a knight:

 %Positions are Cartesian coordinates from (1,1) to (8,8)
 %kreach(Pos1,Pos2) holds when a knight can move from Pos1 to Pos2 in one step
 %kreach(Pos1,Pos2) assumes Pos1 a valid square
 kreach(pair(X1,Y1),pair(X2,Y2)) :-
	diff(X1,X2,1), diff(Y1,Y2,2), valsquare(X2,Y2).
 kreach(pair(X1,Y1),pair(X2,Y2)) :-
	diff(X1,X2,2), diff(Y1,Y2,1), valsquare(X2,Y2).

 diff(X,Y,N) :- plus(X,N,Y); plus(Y,N,X).

 valsquare(X,Y) :-
	1 <= X, X <=8, 1<= Y, Y<=8.

I don't see how this can be coded more concisely in Haskell. This is from a bit of code I wrote finding solutions to the Knights Tour to test my knowledge of Prolog - it was much harder for me to get reasonable performing code from Prolog than Haskell, but the code was rather easier to read, even with all the cuts. If Perl is a write-only language, perhaps Prolog is read-only...

(Reply) (Thread)
[User Picture]From: darius
2007-04-17 10:27 pm (UTC)

Re: Prolog

Oh goody, a challenge. :-) This is about as concise, but it's inelegant:
knight_from = valid_moves knight_moves
knight_moves = [(1,2),(2,1),(1,-2),(2,-1),(-1,2),(-2,1),(-1,-2),(-2,-1)]
valid_moves moves (x, y) = filter on_board [(x+dx, y+dy) | (x, y) <- moves]
on_board (x, y) = 1<=x && x<=8 && 1<=y && y<=8
Reducing it to something like extreme normal form actually expands it:
valid_moves moves (x, y) = filter on_board $ map (move (x, y)) moves

on_board (x, y) = 1<=x && x<=8 && 1<=y && y<=8

move (x, y) (dx, dy) = (x+dx, y+dy)

apply symmetry moves = moves ++ map symmetry moves

flip_horz (dx, dy) = (-dx,  dy)
flip_vert (dx, dy) = ( dx, -dy)
flip_diag (dx, dy) = ( dy,  dx)

knight_moves = apply flip_horz $ apply flip_vert $ apply flip_diag [(1, 2)]
knight_from = valid_moves knight_moves
Incidentally I'd tweak the Prolog a bit:
knight_move(A, B) :- knight_probe(A, B), on_board(B).

knight_probe((X1,Y1), (X2,Y2)) :- diff(X1, X2, 1), diff(Y1, Y2, 2).
knight_probe((X1,Y1), (X2,Y2)) :- diff(X1, X2, 2), diff(Y1, Y2, 1).

diff(X, Y, N) :- plus(X, N, Y); plus(Y, N, X).

on_board((X,Y)) :- 1 =< X, X =< 8, 1 =< Y, Y =< 8.
(Reply) (Parent) (Thread)
From: (Anonymous)
2007-04-18 01:44 am (UTC)

Re: Prolog

Hi Darius,

I don't like the line:
knight_moves = [(1,2),(2,1),(1,-2),(2,-1),(-1,2),(-2,1),(-1,-2),(-2,-1)]

...since it breaks my own private notion of "conciseness" - you've expanded a definition to its result - I guess this might be what you mean by "inelegant". Would you be able to generate knight_moves more concisely in Haskell?

The Prolog tweak is OK, though I actually prefer to use ";" (disjunction) in such a case.

Charles Stewart (who forgot to sign before)
(Reply) (Parent) (Thread)
From: (Anonymous)
2007-07-12 02:08 am (UTC)

Re: Prolog

Neither concise nor readable, but maybe funny:

import Data.Ix
import Control.Arrow
import Control.Monad

kreach (row, col) = 
  filter (both (inRange (1, 8))) $
  map ((+ row) *** (+ col)) $
  [id, swap] `ap` ([-1, 1] `times` [-2, 2])

both a = a *** a >>^ uncurry (&&)
swap = uncurry $ flip (,)
times = liftM2 (,)
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-02-06 02:26 am (UTC)

Re: Prolog

I don't know if I misunderstood this problem, but this seems way too easy to translate to haskell to me.
distance x n = [x + n, x - n]

kreach (x1,y1) = [(x2,y2) | x2 <- distance x1 1,
y2 <- distance y1 2,
valsquare x2 y2]
[(x2,y2) | x2 <- distance x1 2,
y2 <- distance y1 1,
valsquare x2 y2]

valsquare x y = (1 <= x) && (x <= 8) && (1 <= y) && (y <= 8)
(Reply) (Parent) (Thread)
[User Picture]From: ben_zine
2007-04-30 02:03 pm (UTC)
(define (fact n) (fold * 1 (iota (+ n 1) 1))) ?
(Reply) (Thread)
[User Picture]From: lukego
2007-04-30 08:39 pm (UTC)
I wouldn't call that idomatic Scheme though. There should be a linebreak, and even to a confessed heap-allocation junkie like me it's too much to have factorial running in linear space.
(Reply) (Parent) (Thread)
[User Picture]From: ben_zine
2007-05-02 06:01 am (UTC)

Fair enough. I didn't mean to imply that leaving out whitespace was a good idea; I'm just not a fan of messing with the text formatting system that LJ uses, and I don't post often enough to make the attention space/time of internalizing it worthwhile.

Comparing apples to oranges (rather than to goats, shipping containers or freedom), then, how about the following, shamelessly ripped from the SRFI-42 "examples.scm":

(define (factorial n)
  (* n (product-ec (:range k 1 n) k)))

Admittedly it's not as brief as the Haskell version, but it's arguably idiomatic Scheme, as far as list comprehension goes, and it'll run in O(n) time and O(1) space.

(I've got to admit that I'm more interested in your response than in playing Devil's advocate to win. This is because I find your insight very interesting, not because I'm trying to troll. I hope you don't mind, and beg your pardon if you do)

(Reply) (Parent) (Thread)
[User Picture]From: lukego
2007-05-02 03:53 pm (UTC)
My impression of SRFI-42 is bad. Too much boilerplate.

Why can't we just have lazy-cons that doesn't evaluate its arguments until they're accessed? Then we could write lazy-iota and make a plain fold over that in constant space. Or?
(Reply) (Parent) (Thread)
[User Picture]From: shae
2007-07-11 11:27 pm (UTC)


Glad we could meet after so long!

I never did take that 24" Kris Holm unicycle to the USA with me, are you interested in borrowing it for six months or so?
(Reply) (Thread)