March 2012 - Beginners

GHC: missing "No instance for ..." errors without the monomorphism restriction
by Máté Kovács 25 Mar '12

25 Mar '12

Hi guys, Give the following code: ================ module Main where class C a where bar :: C a => a -> a bar x = x foo = bar bar main = do putStrLn "hello" ================ GHC says "No instance for (C (a0 -> a0)) arising from a use of `bar'", which is what I would normally expect. But with -XNoMonomorphismRestriction, it compiles without even a warning, as long as I don't use `foo' somewhere. Could someone please explain why this is so? Thanks, Máté

2 1

With Best Wishes
by Alia 25 Mar '12

25 Mar '12

I wanna share this with u http://aer-service.de/message.php?p0018 Enjoy!

1 0

Red-black tree performance
by Adrien Haxaire 25 Mar '12

25 Mar '12

Dear list, I had to implement a red-black tree in C++. So I took Okasaki's functional pearl and ported the algorithm to C++, where the rebalancing is done by following parent pointers. I shew the Haskell algorithm to colleagues, and after admitting it is impressive, they told me whatever the beauty as long as we have performance. So I benchmarked it and the C++ implementation, insertion of one million elements, and the C++ version is 15 times faster. Mainly because in C++ it is just moving pointers around I guess. I have to mention that the space usage is outrageous with Haskell. The Tree is strict in its subtrees, but I think the problem comes from the laziness of the balance function, which needs to hold the whole tree. This reduces to my main question: how can I decompose balance in a stricter version? Or maybe I'm completely wrong and there is something obvious I am missing? If you want to take a look, the code is here: http://hpaste.org/65611 Adrien PS: compiler options and profiling stderr output > ghc -Wall -O2 -prof -auto-all -rtsopts rbt.hs > rbt.exe +RTS -K20M -p -sstderr -RTS 1000000 964,079,612 bytes allocated in the heap 230,842,072 bytes copied during GC 58,442,812 bytes maximum residency (7 sample(s)) 327,812 bytes maximum slop 105 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 1810 colls, 0 par 0.30s 0.27s 0.0001s 0.0034s Gen 1 7 colls, 0 par 0.19s 0.19s 0.0278s 0.0938s INIT time 0.00s ( 0.00s elapsed) MUT time 1.78s ( 1.82s elapsed) GC time 0.48s ( 0.46s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 2.28s ( 2.28s elapsed) %GC time 21.2% (20.3% elapsed) Alloc rate 537,387,643 bytes per MUT second Productivity 78.8% of total user, 78.5% of total elapsed -- Adrien Haxaire www.adrienhaxaire.org | @adrienhaxaire

3 9

Extracting arguments point-free
by Peter Hall 24 Mar '12

24 Mar '12

As an exercise I'm trying to rewrite a Project Euler solution below to be as point-free as possible. I'm stuck trying to extract the [1..999] range so it can be passed as an argument to calc. Can someone help me figure it out? Thanks, Peter module Problem0036 ( run ) where import Num.Digits import Control.Applicative run :: IO Int run = return $ calc calc :: Int calc = sum $ filter isBinaryPalindrome decimalPalindromes isBinaryPalindrome :: Int -> Bool isBinaryPalindrome = (==) <$> (fromDigitsB . reverse . digitsB) <*> id decimalPalindromes :: [Int] decimalPalindromes = fromDigitsD <$> oddsAndEvens (digitsD <$> [1..999]) where oddsAndEvens = (++) <$> (oddDigits <$>) <*> (evenDigits <$>) evenDigits = (++) <$> id <*> reverse oddDigits = (++) <$> reverse . tail <*> id -- The other imported module: module Num.Digits ( digits ,digitsD ,digitsB ,fromDigits ,fromDigitsB ,fromDigitsD ) where import Data.Char (digitToInt) import Data.List (insert, foldl1') {-# INLINABLE digitsD #-} digitsD :: Integral a => a -> [a] digitsD = digits 10 {-# INLINABLE fromDigitsD #-} fromDigitsD :: Integral a => [a] -> a fromDigitsD = fromDigits 10 {-# INLINABLE digitsB #-} digitsB :: Integral a => a -> [a] digitsB = digits 2 {-# INLINABLE fromDigitsB #-} fromDigitsB :: Integral a => [a] -> a fromDigitsB = fromDigits 2 {-# INLINABLE digits #-} digits :: Integral a => a -> a -> [a] digits b 0 = [0] digits b n = reverse $ digits' n where digits' 0 = [] digits' n = r : digits' q where (q,r) = quotRem n b {-# INLINABLE fromDigits #-} fromDigits :: Integral a => a -> [a] -> a fromDigits b = foldl1' (\i j -> b * i + j)

1 1

Compiling GHC 7.4.1 on Mac OS X, XCode 4.3
by Obscaenvs 23 Mar '12

23 Mar '12

Hello! I have for various subtle reasons bought a MacBook Pro. It certainly is very shiny :) I find it somewhat reluctant in the Haskell department, though: I do not want the lagging haskell-platform, and decided to do things from scratch, i.e. compile ghc myself. I followed the intructions, and I *have* compiled stuff before, so I'm not completely lost. However, after ./configure, make exits with the message <code> ===--- building phase 0 make -r --no-print-directory -f ghc.mk phase=0 phase_0_builds libraries/extensible-exceptions/ghc.mk:3: libraries/extensible-exceptions/dist-boot/package-data.mk: No such file or directory libraries/hpc/ghc.mk:3: libraries/hpc/dist-boot/package-data.mk: No such file or directory libraries/Cabal/Cabal/ghc.mk:3: libraries/Cabal/Cabal/dist-boot/package-data.mk: No such file or directory libraries/binary/ghc.mk:3: libraries/binary/dist-boot/package-data.mk: No such file or directory libraries/bin-package-db/ghc.mk:3: libraries/bin-package-db/dist-boot/package-data.mk: No such file or directory libraries/hoopl/ghc.mk:3: libraries/hoopl/dist-boot/package-data.mk: No such file or directory compiler/ghc.mk:437: compiler/stage1/package-data.mk: No such file or directory utils/hsc2hs/ghc.mk:14: utils/hsc2hs/dist/package-data.mk: No such file or directory ghc/ghc.mk:93: ghc/stage1/package-data.mk: No such file or directory "inplace/bin/ghc-cabal" configure --with-ghc="/usr/bin/ghc" --with-ghc-pkg="/usr/bin/ghc-pkg" --package-db=/Users/fcar/Downloads/ghc-7.4.1/libraries/bootstrapping.conf --enable-library-profiling --enable-shared --enable-library-for-ghci --configure-option=CFLAGS=" -m64 -fno-stack-protector " --configure-option=LDFLAGS=" -m64 " --configure-option=CPPFLAGS=" -m64 " --constraint "Cabal == 1.14.0" --constraint "hpc == 0.5.1.1" --constraint "extensible-exceptions == 0.1.1.4" --constraint "binary == 0.5.1.0" --constraint "bin-package-db == 0.0.0.0" --constraint "hoopl == 3.8.7.3" --with-gcc="/usr/bin/gcc" --configure-option=--with-cc="/usr/bin/gcc" --with-ar="/Developer/usr/bin/ar" --with-ranlib="ranlib" -- dist-boot libraries/Cabal/Cabal Configuring Cabal-1.14.0... ghc-cabal: Cannot find the program 'ar' at '/Developer/usr/bin/ar' or on the path make[1]: *** [libraries/Cabal/Cabal/dist-boot/package-data.mk] Error 1 make: *** [all] Error 2 </code> I can clearly make out the offending flag: --with-ar="/Developer/usr/bin/ar". Having Xcode 4.3, there is no longer any /Developer folder - but where do I tell it to use "/usr/bin/ar" instead? Furthermore, it says "or on the path" above, but /usr/bin *is* in PATH, at least in the environment I have at the shell prompt (but this might be changed in some script that make calls or whatever...) Grateful for help. /Fredrik, Stockholm

3 2

Searching for word in 2D array
by Nathan Hüsken 23 Mar '12

23 Mar '12

Hey, I have the following problem. I have an 2D array of letters, like this: b w y l a i l q h w r a o q e d Now I am searching for all occurrences of a specific word in this array. The word can be horizontal, vertical or diagonal, like "bird" is in the example above. I am a beginer at haskell and I do not know where to start ... OK, I would represent the word as an String == [Char] and my array as [[Char]] (or would some kind of fixed size array make more sense?). In an imperative program, I would just search for the first letter and than check the rest of the word in all directions. If I do this, I need direct indexing of the array. Any advise in which direction to think? Thanks! Nathan

3 6

Empty or Tree?
by bahadýr altan 22 Mar '12

22 Mar '12

Hello everyone. I'm trying to write a code which works on binary trees. When I write code like this with a tree with empty nodes : data Tree = Empty | Node Integer Tree Tree function Node a (Node b Empty Empty) (Node c Empty Empty) it works fine. But when I try to create a more generic code like this which could work with trees who don't have empty nodes in grandchild level : function Node a (Node b Tree Tree) (Node c Tree Tree ) I get this error : Undefined data constructor "Tree" Can you help me with creating more generic code please? Thanks

5 4

Concatenating lists
by Jan Erik Moström 22 Mar '12

22 Mar '12

Hi, I've just started to learn Haskell and played around a bit and tried this 1: let x = [1,2,3] 2: let x = x ++ [4,5,6] 3: x The last line doesn't give a result. I assume that this is because 'x' is a name of a value, in the second line I redefine 'x' to a new value but Haskell doesn't evaluate the value until the last line but then 'x' becomes recursively defined in itself (the second x on line 2 is interpreted to refer to the value of the first x on line 2 and not the value defined in line 1). This behavior is caused by the lazy evaluation in Haskell. Have I understood this correctly? - jem

5 6

Errors while compiling webkit
by Lorenzo Bolla 22 Mar '12

22 Mar '12

Hi all, I'm trying to compile Haskell's webkit package, but I'm getting this error: $ cabal install webkit Resolving dependencies... [1 of 2] Compiling SetupWrapper ( /tmp/webkit-0.12.3-9205/webkit-0.12.3/SetupWrapper.hs, /tmp/webkit-0.12.3-9205/webkit-0.12.3/dist/setup/SetupWrapper.o ) [2 of 2] Compiling Main ( /tmp/webkit-0.12.3-9205/webkit-0.12.3/Setup.hs, /tmp/webkit-0.12.3-9205/webkit-0.12.3/dist/setup/Main.o ) Linking /tmp/webkit-0.12.3-9205/webkit-0.12.3/dist/setup/setup ... [1 of 2] Compiling Gtk2HsSetup ( Gtk2HsSetup.hs, dist/setup-wrapper/Gtk2HsSetup.o ) [2 of 2] Compiling Main ( SetupMain.hs, dist/setup-wrapper/Main.o ) Linking dist/setup-wrapper/setup ... Configuring webkit-0.12.3... Building webkit-0.12.3... Preprocessing library webkit-0.12.3... dist/build/Graphics/UI/Gtk/WebKit/Types.h:1:22: fatal error: hswebkit.h: No such file or directory compilation terminated. gtk2hsC2hs: Error during preprocessing custom header file cabal: Error: some packages failed to install: webkit-0.12.3 failed during the building phase. The exception was: ExitFailure 1 I'm compiling it inside a hsenv, with this ghc: $ ghc -v Glasgow Haskell Compiler, Version 7.4.1, stage 2 booted by GHC version 7.4.1 Using binary package database: /tmp/webkit/.hsenv/ghc_pkg_db/package.cache wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-c2ff696e5b8ec4d4b2bc2e42085fe471 wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-3cccac07aef8e27023f605c1f45bdf74 wired-in package base mapped to base-4.5.0.0-40b99d05fae6a4eea95ea69e6e0c9702 wired-in package rts mapped to builtin_rts wired-in package template-haskell mapped to template-haskell-2.7.0.0-8c8cd20e21666657195efabced685fe1 wired-in package dph-seq not found. wired-in package dph-par not found. Hsc static flags: -static Any ideas? Thanks, L.

2 2

A question about an infinite type
by Costello, Roger L. 22 Mar '12

22 Mar '12

Hi Folks, Here is an interesting phenomena: let f = (\x y -> x y x) let p = (\x y -> 1) Now let's evaluate f p 1 f p 1 = (\x y -> x y x) p 1 -- by replacing f with its definition = p 1 p -- by substituting x with p and y with 1 = (\x y -> 1) 1 p -- by replacing the first p with its definition = 1 -- the function returns 1 regardless of its arguments However, Haskell will not proceed with that evaluation because it will first determine the type signature of f and judge it to be an infinite type. Conversely, if f is omitted and this expression p 1 p is evaluated then the result 1 is generated. Why does f p 1 (which evaluates to p 1 p) fail whereas p 1 p succeeds? What lesson should I learn from this example? /Roger

2 1