Tuesday, 14 August 2007

Power Set

The Haskell community are discussing the confusion surrounding Monads on their mailing list at the moment. The example of a function to compute the powerset in Haskell using the List monad was given:

$ ghci
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.6.1, for Haskell 98.
/ /_\\/ __ / /___| | http://www.haskell.org/ghc/
\____/\/ /_/\____/|_| Type :? for help.

Loading package base ... linking ... done.
Prelude> :m + Control.Monad
Prelude Control.Monad> let powerset = filterM (const [True, False])
Prelude Control.Monad> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

This is an impressive one-liner. However, it took me the best part of an hour to get it to run, by discovering that "import name" in compiled Haskell source code is written ":m + name" when you're writing interactively in GHCi, and "powerset = filterM (const [True, False])" must be preceded by "let".

I thought I'd post an OCaml equivalent, complete with the response of the top-level:

$ ocaml
Objective Caml version 3.10.0

# let rec powerset = function


| [] -> [[]]


| h::t -> List.fold_left (fun xs t -> (h::t)::t::xs) [] (powerset t);;


val powerset : 'a list -> 'a list list =


# powerset [1;2;3];;


- : int list list = [[1; 3]; [3]; [1; 2; 3]; [2; 3]; [1]; []; [1; 2]; [2]]


I hadn't really appreciated until now that OCaml code is the same whether you compile it or enter it into the interactive top-level, except for the ";;" suffix to get the interactive mode to evaluate.

No comments: