8 replies to this topic

[CChris]

Hi all,

I'm trying to teach myself Haskell, and given my imperative background, this is the most mind-warping thing I've had to do in years.

Since there is no Haskell forum here, and really no Haskell forum any place on the internet, I'm posting this in General Programming. I'm sure anyone with any Haskell experience should be able to help with my problem.

Right. I'm trying to write a function cprod to find the cartesian product of a list of lists. For instance,

cprod [[1, 2, 3], [4], [5, 6]]

  = [[1, 4, 5], [1, 4, 6], [2, 4, 5], [2, 4, 6], [3, 4, 5], [3, 4, 6]]

I've got some imperative code that does the job fine in a Pythonesque programming language, so I understand how to solve the problem. However, I don't know how to express it in Haskell's strange syntax, and that's where I need some help.

Here's the imperative code that I know works:

define foo(list, res);

    if list = nil then

        return res;

    endif;


    for i in hd(list) do

        foo(tl(list), res + i);

    endfor;

enddefine;


[% foo([[1 2 3] [4] [5 6]], []); %]

I know that's in a language even more obscure than Haskell (can anyone guess what?), but it should be quite readable.

I'm trying to write that out in Haskell using just recursion for now (so, no fancy foldr or whatever), and this is how far I've gotten so far:

foo list res 

    | list == []  = res

    | otherwise   = [ foo (tail list) (res ++ [x]) | x <- head (head list) ]

That code gives this error when being loaded into Hugs:

ERROR - Type error in application

*** Expression     : foo2 (tail list) [x]

*** Term           : tail list

*** Type           : [[[a]]]

*** Does not match : [a]

*** Because        : unification would give infinite type

which, unfortunately, means absolutely nothing to me.

Could anyone please prod me in the right direction?

Many thanks,
CChris

[WingedPanther]

I think you're approaching this completely wrong (having just started to learn Haskell today).

Start by thinking clearly about what you want to accept and return. Based on what you've got initially, we'll need the following type definition for cprod:

cprod :: [[a]] -> [[a]]

So, cprod takes a list of lists and returns a list of lists. We don't care what they're lists of. In addition, it is easier to deal with thinking about two things at once. Cartesian products are really a binary operation, where [[1,2,3]] cart [[4]] = [[1,4],[2,4],[3,4]]
then
[[1,4],[2,4],[3,4]] cart [[5,6]] = [[1, 4, 5], [1, 4, 6], [2, 4, 5], [2, 4, 6], [3, 4, 5], [3, 4, 6]]

This suggests we should create a helper function binarycart that is recursive. Working quickly, I got this much (which doesn't work right). The problem's in binarycart.

binarycart :: [a] -> [[a]] -> [[a]]
binarycart x [] = [x]
binarycart x (y:z) = [ a:b | a <- x, b <- binarycart y z ]

cprod :: [[a]] -> [[a]]
cprod [[]] = [[]]
cprod (x:[]) = [x]
cprod (x:y) = binarycart x y

[CChris]

Thanks for the reply, WingedPanther! It showed me a lot of tricks I didn't know.

I now have this:

foo [] r      = [r]

foo list res  = forin (head list) list res


forin (x:[]) (y:ys) r = foo ys (r ++ [x])

forin (x:xs) list res = (foo (tail list) (res ++ [x])) ++ (forin (tail xs) list res)

And of course, it doesn't work. It should, but it doesn't. I get this error:

foo [[1,2,3],[4],[5,6]] []

[[1,4,5]

Program error: pattern match failure: forin [] [[5,6]] [1,4]

Can't see how it gets forin [] ...
Any ideas?

[CChris]

Indeed, FAIL. :thumbdown:
Haskell is what I call software engineering suicide.

Amongst all the gibberish was an unneeded symbol, now removed:

foo [] r      = [r]

foo list res  = forin (head list) list res


forin (x:[]) (y:ys) r = foo ys (r ++ [x])

forin (x:xs) list res = (foo (tail list) (res ++ [x])) ++ (forin xs list res)

And after two days of work, I have this thing working.

Phew! Now, to figure out how to do this with list comprehension + foldl...

[WingedPanther]

I just started learning it from a tutorial yesterday. My thinking is that Haskell, more than any other language, forces you to start VERY small and build up slowly. Trying to think big and refine in seems to be a great way to get a headache.

[CChris]

I'm already becoming pretty comfortable with the syntax, despite it being such an eyesore. I wouldn't ever let a stupid little programming language bring me down or hold me back.

Though I do feel like I'm very far away from the land of code clarity (from no fault of my own)... basically, bring back Python! Screw the theoretical advantages of pure functional programming -- if you can't read it, what good is it?

I'll persevere.

[Sinipull]

I'm taking course for Haskell this semester. Also course for Prolog, which is purely logic programming.

Both are totally different from imperative languages and from each other, and i still haven't figured out, what's so great about them, that i couldn't achieve by using imperative languages...

I have a little over 10 days to learn Haskell from scratch, cause i'm pretty lazy and haven't studied anything over the previous 1.5 months.

Anyway, good luck.

[CChris]

Lazy evaluation -- see, at least you're in the right mindset.

In many ways, learning one of those languages will teach you a lot about the other. Prolog is very good for writing parsers (but sucks for anything else). Haskell is supposedly safer to use than imperative languages (because it doesn't allow assignment and programs are easier to analyse and detect mistakes), and it has some potential where it comes to concurrency.

Haskell is more difficult than Prolog, but possibly more useful in the long run. Prolog is a very small language compared to Haskell, and may be possible to learn in 10 days. You choose how you want to use your time.

[WingedPanther]

Haskell's native support for arbitrary precision integers, and strong math orientation strikes me as a strong recommendation for using it on some of the Euler challenges.

Things like the ability to define a list of ALL primes, and use lazy evaluation to generate the ones needed on the fly strikes me as very useful.