January 2010 - Haskell-Cafe

Help with Bird problem 3.3.3
by Peter Hilal 11 Jun '10

11 Jun '10

I'm working my way through Bird's _Introduction to Functional Programming Using Haskell_. I'd appreciate any help with problem 3.3.3, which is: "Division of natural numbers can be specified by the condition (n * m) / n = m for all positive n and all m. Construct a program for division and prove that it meets the specification." The required construction relies on the following definitions: data Nat = Zero| Succ Nat (+) :: Nat -> Nat m + Zero = m m + Succ n = Succ (m + n) (*) :: Nat -> Nat m * Zero = Zero m * Succ n = m * n + m Proceeding as Bird does in Sec. 3.2.2, where he derives the definition of "-" from the specification "(m + n) - n = m", I've so far gotten the first case, in which m matches the pattern "Zero", simply by (i) substituting Zero for m in the specification, (ii) substituting Succ n for n in the specification (solely because n is constrained to be positive), and (iii) reducing by applying the first equation of "*": Case Zero: (Succ n * Zero) / Succ n = Zero ≡ {first equation of "*"} Zero / Succ n = Zero Easy enough, and completely intuitive, since we expect Zero divided by any non-Zero finite number to be Zero. The next case, in which m matches the pattern "Succ m", is where I get stuck, and I really have no intuition about what the definition is supposed to be. My first step is to substitute "Succ m" for "m" in the given specification, and to substitute Succ n for n in the specification (for the same reason, as above, that n is constrained to be positive), and then to use the definition of "*" to reduce the equation: Case Succ m: Succ n * Succ m / Succ n = Succ m ≡ {second equation of "*"} (Succ n * m + Succ n) / Succ n = Succ m Where do I go from here? Thank you so much.

5 4

GHC 6.12 on OS X 10.5
by Conor McBride 08 May '10

08 May '10

Hi I thought I'd record my upgrade exerience (so far) in case anyone else finds it useful, and (more selfishly) in case anyone has some helpful advice. Summary of situation * I got 6.12 working. * It took a lot of fumbling around. * The eventual "fix" (renaming /opt/local/lib/libiconv.dylib) was a bit dodgy, but is holding for now. Long rambling narrative follows. Various features of GHC 6.12 made it very tempting to go for an earlier upgrade than I normally would. (SHE really needs GADT-style data families; everything I do needs deriving Traversable (deriving HalfZip would be nice too!).) Already there was a handy installer for Intel+Leopard macs (is anybody on the PPC+Leopard case? if not, I will be soon...). I thought "go for it". Installation, no problem. Compiling something: whoops, no mtl. OK, cabal install mtl: whoops, no acceptable cabal. Fair dos, if I'd read the warnings I'd have known that my cabal-install would be useless and tried to build the new one. QUESTION: Is the sensible upgrade path to build cabal-install 0.8 with your old GHC, before installing 6.12? Does this even work? At one point, I tried this and had some peculiar issues involving zlib... Anyhow, I've got 6.12 and I need cabal-install 0.8. Can I find it? Tricky, and http://haskell.org/cabal/ didn't help much. I'm very tolerant of busy people not quite getting round to it, and I can use google, so I find the darcs version and get cracking. This happens: ----------------------------------------------------------------------------- bash-3.2$ ./bootstrap.sh Checking installed packages for ghc-6.12.1... parsec-2.1.0.1 will be downloaded and installed. network-2.2.1.5 will be downloaded and installed. Cabal is already installed and the version is ok. mtl-1.1.0.2 will be downloaded and installed. HTTP-4000.0.8 will be downloaded and installed. zlib-0.5.2.0 will be downloaded and installed. Downloading parsec-2.1.0.1... % Total % Received % Xferd Average Speed Time Time Time Current Dload Upload Total Spent Left Speed 100 15430 100 15430 0 0 12743 0 0:00:01 0:00:01 --:--:-- 19312 [1 of 1] Compiling Main ( Setup.hs, Setup.o ) Linking Setup ... Undefined symbols: "_iconv_close", referenced from: _hs_iconv_close in libHSbase-4.2.0.0.a(iconv.o) "_iconv", referenced from: _hs_iconv in libHSbase-4.2.0.0.a(iconv.o) "_iconv_open", referenced from: _hs_iconv_open in libHSbase-4.2.0.0.a(iconv.o) ld: symbol(s) not found collect2: ld returned 1 exit status Error during cabal-install bootstrap: Compiling the Setup script failed ----------------------------------------------------------------------------- At lthis point, I suspected a linker/dylib problem, but foolishly, I wanted the problem to be pretty much anything else, so I spent far too long looking the wrong way. I thought that if I could just get cabal-install working somehow, I'd be ok. I tried installing parsec with runhaskell Setup.hs {configure,build,install} but each of these commands appeared content to do precisely nothing: I found this perplexing. I tried reverting to 6.10.4 and compiling cabal-install. This made more progress, but died with some sort of zlib version snafu. (I'm sorry, I should have recorded the details but didn't.) The zlib-0.5.2.0 package did install successfully, but somehow the build for cabal-install itself went awry with an "even though this is the right version I can't find X" sort of a problem. I uninstalled 6.10.4, deleted my .cabal directory, nuked a few other relics showing up from what's probably a dumb choice of PATH setting. I had another go at 6.12, and this time I tried compiling a wee program of my own with no exciting package dependencies. Should have done that straight away, of course. Same iconv problem. This left no alternative. I found I had a /usr/lib/libiconv.dylib etc and an /opt/local/lib/libiconv.dylib etc, so I renamed the latter to opt/local/lib/moolibiconv.dylib, and suddenly, GHC became capable of linking stuff. The darcs version of cabal-install then built just fine; SHE rebuilt ok; Epigram needed a few extra LANGUAGE pragmas, but no trouble. I'm almost back where I was. I worry about this. (1) What have I broken by shifting the opt/local/lib copy of libiconv? (2) Why did that break things anyway? (3) How come I ended up with a broken library setup? (4) What else is broken? (What's worse than finding a maggot in your apple? Finding half a maggot in your apple.) I'm not at all a mac expert (I use a mac because I'm too stupid to maintain a linux installation -- the Nottingham grad students (all grown up now) told me they were fed up fixing my computer back in 04.) This dylib nonsense seems quite common. Is it MacPorts messing things up? Is there a more principled fix than the brutal thing I did? I wonder if it might be possible to build some sort of diagnostic tool to check paths and libraries for conflicts and omissions. Anyhow, sorry for the dreariness of this story, but it ends in an acceptable configuration, for the moment. I hope it can be of some small help. Happy hols Conor

10 19

really difficult for a beginner like me...
by Ivan Amarquaye 24 Mar '10

24 Mar '10

Hi everyone, this is my first posting on here and this was what drove me here and the quest to know more as i anticipate a lot of help and direction in this quite new and different environment haskell.I have this paper that i'm working on and need to solve these scenarios/ cases based on some sample codes: Scenarios/cases: 1) Allow words to be hyphenated and treat the hyphenated word as a single word (including the hyphen). 2) As for no. 2 but if the hyphen is the last character on a line treat the hyphenated word as a single word without the hyphen. 3) Treat a capitalised word (one or more capital letters) the same as lower case, i.e. only the lower case word appears in the index. 4) Treat a word ending in an ‘s’ as a plural and thus the same as the singular, i.e. only the singular appears in the index. 5) As for no. 5 but (a) treat suffix ‘ss’ as not a plural; and (b) treat the plural suffixes ‘sses’, ‘zzes’, ‘oes’, ‘xes’, ‘shes’, ‘ches’ the same as the singular, i.e. without the ‘es’, e.g. “branches” (except for 4- and 5-letter plurals with suffices ‘oes’ and ‘ches’, e.g. “floes”, and 4-letter plural suffix ‘xes’); and (c) treat the plural suffix ‘ies’ (except for 4-letter plurals, e.g. “pies”) as the singular suffix ‘y’. 6) Make the output more readable in the form of an index table. 7) Use an output file 8) Include a user-friendly menu by which the user can choose input and output file names. This is the code i'm supposed tomodify and in some cases create new functions to support.I also need some explanation as the various approaches in solving them.............................................................................................. The function makeIndex given a document produces a list of entries. Each entry is a word and a list of line numbers (for words > 4 letters) Type definitions: import Prelude -- hiding (Word) -- predefined Word hidden, so we can define ours -- type String = [Char] defined in Prelude type Doc = String type Line = String type Word = String -- our version makeIndex :: Doc -> [ ([Int], Word) ] A data-directed design considers a sequence of functions (i.e using composition operator ‘.’) to transform the document of type, Doc, into an index of type, [ ([Int], Word) ]. splitUp the document, doc, into a list of lines, [Line]. numLines pairs each line with a line number, [(Int, Line)]. allNumWords splits lines into words and line no., [(Int, Word)]. sortLs sorts words into alphabetical order, [(Int, Word)]. makeLists makes a list for each line number, [([Int], Word)]. amalgamate nos. into a list of nos. for each word, [([Int], Word)]. shorten into a list for words > 4 letters, [([Int], Word)]. makeIndex = shorten . -- [([Int], Word)] -> [([Int], Word)] amalgamate . -- [([Int], Word)] -> [([Int], Word)] makeLists . -- [(Int, Word)] -> [([Int], Word)] sortLs . -- [(Int, Word)] -> [(Int, Word)] allNumWords . -- [(Int, Line)] -> [(Int, Word)] numLines . -- [Line] -> [(Int, Line)] splitUp -- Doc -> [Line] Last -- [a] -> [a ] splitUp function splitUp :: Doc -> [Line] splitUp [] = [] splitUp text = takeWhile (/='\n') text : -- first line (splitUp . -- splitup other lines dropWhile (==’\n’) . -- delete 1st newline(s) dropWhile (/='\n')) text -- other lines Example: splitUp “hello world\n\nnext world” => [“hello world”, “next world”] numLines function: numLines :: [Line] -> [(Int, Line)] numLines lines -- list of pairs of = zip [1 .. length lines] lines -- line no. & line Example: numLines [“hello world”, “next world”] => [(1, “hello world”), (2, “next world”)] splitWords function: -- for each line -- a) split into words -- b) attach line no. to each word splitWords :: Line -> [Word] -- a) splitWords [ ] = [ ] splitWords line = takeWhile isLetter line : -- first word in line (splitWords . -- split other words dropWhile (not.isLetter && Last ==’-’) . -- delete separators dropWhile isLetter) line -- other words where isLetter ch = (‘a’<=ch) && (ch<=’z’) || (‘A’<=ch) && (ch<=’Z’) Example: splitWords “hello world” => [“hello”, “world”] allNumWords function: numWords :: (Int, Line) -> [(Int, Word)] -- b) numWords (number, line) = map addLineNum ( splitWords line) -- all line pairs where addLineNum word = (number, word) -- a pair allNumWords :: [(Int, Line)] -> [(Int, Word)] allNumWords = concat . map numWords -- doc pairs Examples: addLineNum “hello” => (1, “hello”) numWords (1, “hello world”) => [(1, “hello”), (1, “world”)] allNumWords [(1, “hello world”), (2, “next world”)] => [(1, “hello”), (1, “world”), (2, “next”), (2, “world”)] SortLs function: sortLs :: [(Int, Word)] -> [(Int, Word)] sortLs [ ] = [ ] sortLs (a:x) = sortLs [b | b <- x, compare b a] -- sort 1st half ++ [a] ++ -- 1st in middle sortLs [b | b <- x, compare a b] -- sort 2nd half where compare (n1, w1) (n2, w2) = (w1 < w2) -- 1st word less || (w1 == w2 && n1 < n2) -- check no. Example: sortLs [(1, “hello”), (1, “world”), (2, “next”), (2, “world”)] => [(1, “hello”), (2, “next”), (1, “world”), (2, “world”)] makeLists function: makeLists :: [(Int, Word)] -> [([Int], Word)] makeLists = map mk -- all pairs where mk (num, word) = ([num], word) -- list of single no. Examples: mk (1, “hello”) => ([1], “hello”) makeLists [(1, “hello”), (2, “next”), (1, “world”), (2, “world”)] => [([1], “hello”), ([2], “next”), ([1], “world”), ([2], “world”)] Amalgamate function: amalgamate :: [([Int], Word)] -> [([Int], Word)] amalgamate [ ] = [ ] amalgamate [a] = [a] amalgamate ((n1, w1) : (n2, w2) : rest) -- pairs of pairs | w1 /= w2 = (n1, w1) : amalgamate ((n2, w2) : rest) | otherwise = amalgamate ((n1 ++ n2, w1) : rest) -- if words are same grow list of numbers Example: amalgamate [([1], “hello”), ([2], “next”), ([1], “world”), ([2], “world”)] => [([1], “hello”), ([2], “next”), ([1, 2], “world”)] Shorten function: shorten :: [([Int], Word)] -> [([Int], Word)] shorten = filter long -- keep pairs >4 where long (num, word) = length word > 4 -- check word >4 Example: shorten [([1], “hello”), ([2], “next”), ([1, 2], “world”)] => [([1], “hello”), ([1, 2], “world”)] _________________________________________________________________ Connect to the next generation of MSN Messenger http://imagine-msn.com/messenger/launch80/default.aspx?locale=en-us&source=…

6 8

Anyone up for Google SoC 2010?
by Malcolm Wallace 10 Mar '10

10 Mar '10

Google has announced that the Summer of Code programme will be running again this year. If haskell.org people would like to take part again this year, then we need volunteers: First, * suggestions for suitable projects (in the past this was organised using a reddit) * an administrator to co-ordinate the application to Google (I have done it for the last three years but am very willing to hand on to someone else) Google will accept applications from organisations in the period 8th - 12th March 2010, approx 1900UTC. If haskell.org is accepted again, students can apply between 29th March - 9th April. More volunteers will be required: * to review student applications and choose which to accept * to supervise the accepted students Both of these roles are called "mentor" in the Google system. Putting together a good team of mentors before applying as an organisation is helpful towards us being accepted into the programme. Regards, Malcolm

17 32

New OpenGL package: efficient way to convert datatypes?
by Peter Verswyvelen 05 Mar '10

05 Mar '10

The newest package seems to require using GLdouble/GLfloat. What is the most efficient way to convert Double/Float to GLdouble/GLfloat? I'm currently using realToFrac. But essentially the operation should be a nop on my machine. I haven't looked at the core code yet (on Windows, last time I checked, the ghc-core util did not work, and without it, reading core is even harder) Thanks, Peter

7 13

ANN: uuid-0.1.2
by Mark Lentczner 03 Mar '10

03 Mar '10

Antione and I are please to announce the release of uuid-0.1.2. CHANGES: - added functions toByteString and fromByteString - added 'nil' UUID - added unit tests and benchmarks, built when configured -ftest - major speed up of to/from functions (as well as in general) - added version-3 generation (deterministic based on MD5) - major changes to internal representation - now uses four strict Word32 values - internal ByteSource classes for easy construction (see Builder.hs) - Storable instance now stores in memory as system libraries in C do: 16 bytes derived from the network order of the fields, no matter what the host native endianess is. - fixed bugs in V1 time and clock stepping, and V1 generated values - builds cleanly under GHC's -Wall - added CHANGES file String conversions were sped up 4x to 7x! - Mark Mark Lentczner (MtnViewMark) http://www.ozonehouse.com/mark/

2 2

Lambda's
by Henk-Jan van Tuyl 17 Feb '10

17 Feb '10

I love lambda's: http://hawtness.com/2009/12/30/wtf-girl-photo-more-reasons-why-half-life-is… -- Regards, Henk-Jan van Tuyl -- http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html --

11 11

Linguistic hair-splitting
by Andrew Coppin 16 Feb '10

16 Feb '10

Here's one for you to ponder. 7 is a number. 7 is an integer, and integers are numbers. 7 is not a field. 7 is an element of [at least one] field, but 7 itself is not a field. 7 is not a group. 7 is a member of the set of integers, but the set of integers is not a group either. The set of integers form a group when taken together with the addition operator. (And, actually, forms another, different, group when taken with the multiplication operator.) Now, here's the question: Is is correct to say that [3, 5, 8] is a monad? Is it correct to say that lists are a monad? Or would it be more correct to say that lists "form" a monad?

14 17

Interpreting profiling results
by Patrick LeBoutillier 16 Feb '10

16 Feb '10

Hi, This question didn't get any replies on the beginners list, I thought I'd try it here... I've written (and improved using other solutions I've found on the net) a simple sudoku solver which I'm trying to profile. Here is the code: import Array import List (transpose, nub, (\\)) import Data.List data Sudoku = Sudoku { unit :: Int, cells :: Array (Int, Int) Int, holes :: [(Int, Int)] } cell :: Sudoku -> (Int, Int) -> Int cell s i = (cells s) ! i instance Read Sudoku where readsPrec _ s = [(Sudoku unit cells holes, "")] where unit = length . words . head . lines $ s cells = listArray ((1, 1), (unit, unit)) (map read . words $ s) holes = [ c | c <- indices cells, (cells ! c) == 0] instance Show Sudoku where show s = unlines [unwords [show $ cell s (x,y) | x <- [1 .. unit s]] | y <- [1 .. unit s]] genNums :: Sudoku -> (Int, Int) -> [Int] genNums s c@(i,j) = ([1 .. u] \\) . nub $ used where used = (row s u i j) ++ (col s u i j) ++ (square s sq u i j) u = unit s sq = truncate . sqrt . fromIntegral $ u row s u i j = [cell s (i, y) | y <- [1 .. u]] col s u i j = [cell s (x, j) | x <- [1 .. u]] square s sq u i j = [cell s (x, y) | y <- [1 .. u], x <- [1 .. u], f x i, f y j] where f a b = div (a-1) sq == div (b-1) sq solve :: Sudoku -> [Sudoku] solve s = case holes s of [] -> [s] (h:hs) -> do n <- genNums s h let s' = Sudoku (unit s) ((cells s) // [(h, n)]) hs solve s' main = print . head . solve . read =<< getContents When I compile as such: $ ghc -O2 --make Sudoku.hs -prof -auto-all -caf-all -fforce-recomp and run it on the following puzzle: 0 2 3 4 3 4 1 0 2 1 4 0 0 3 2 1 I get the following profiling report: Fri Jan 1 10:34 2010 Time and Allocation Profiling Report (Final) Sudoku +RTS -p -RTS total time = 0.00 secs (0 ticks @ 20 ms) total alloc = 165,728 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc CAF GHC.Handle 0.0 10.7 CAF Text.Read.Lex 0.0 2.1 CAF GHC.Read 0.0 1.2 square Main 0.0 2.8 solve Main 0.0 1.3 show_aVx Main 0.0 3.7 readsPrec_aYF Main 0.0 60.6 main Main 0.0 9.6 genNums Main 0.0 5.0 cell Main 0.0 1.2 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 1 0 0.0 0.3 0.0 100.0 main Main 186 1 0.0 9.6 0.0 85.6 show_aVx Main 196 2 0.0 3.7 0.0 3.7 cell Main 197 16 0.0 0.0 0.0 0.0 solve Main 188 5 0.0 1.3 0.0 11.8 genNums Main 189 8 0.0 5.0 0.0 10.4 square Main 194 88 0.0 2.8 0.0 3.2 cell Main 195 16 0.0 0.4 0.0 0.4 col Main 192 4 0.0 0.7 0.0 1.1 cell Main 193 16 0.0 0.4 0.0 0.4 row Main 190 4 0.0 0.7 0.0 1.1 cell Main 191 16 0.0 0.4 0.0 0.4 readsPrec_aYF Main 187 3 0.0 60.6 0.0 60.6 CAF GHC.Read 151 1 0.0 1.2 0.0 1.2 CAF Text.Read.Lex 144 8 0.0 2.1 0.0 2.1 CAF GHC.Handle 128 4 0.0 10.7 0.0 10.7 CAF GHC.Conc 127 1 0.0 0.0 0.0 0.0 Does the column 'entries' represent the number of times the function was called? If so, I don't understand how the 'square' function could be called 88 times when it's caller is only called 8 times. Same thing with 'genNums' (called 8 times, and solve called 5 times) What am I missing here? Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

5 6

IDL - compilers
by Günther Schmidt 15 Feb '10

15 Feb '10

Hi, are there any IDL compilers that can create Haskelk modules from header files or type-libs? Günther

3 4