- Beginners - Haskell.org

Re: [Haskell-beginners] first open source haskell project and a mystery to boot
by Alia 14 Oct '11

14 Oct '11

Brent Yorgey wrote: > It must be a problem with the ID3 implementation itself. 'items' is > obviously not empty. So the error must be coming from one of the > calls to 'head' in the ID3 implementation (of which there are > several). The original author (whoever they were) ought to be ashamed > of him/herself. Having bugs in your implementation is excusable, but > using functions like 'head' which can crash is not! ;) Thanks for confirming this. I think it's best not to waste any more time on this. I appreciate your help in any case, AK

1 0

Re: [Haskell-beginners] first open source haskell project and a mystery to boot
by Alia 14 Oct '11

14 Oct '11

<snip Brent Yorgey's very helpful reply> Brent, many thanks for taking the time to think about this. I think your solution totally makes sense, and compiles well. The only thing is that when one tries to run t5 through the runDecisionTree function things get a little weird: *ID3> runDecisionTree t5 (head items) *** Exception: Prelude.head: empty list *ID3> map accuracy [t1, t2, t3, t4, t5] [0.35714285714285715, 0.6428571428571429, 0.7142857142857143, 0.35714285714285715, *** Exception: Prelude.head: empty list Other than that it works perfectly (-: In any case, this may be a problem with the ID3 implementation itself, and I was really more befuddled with the issue of how to tackle the kind of problem that you just solved than in the specifics of the algorithm. If anyone is interested in actually demonstrating that this code is not buggy, here's the complete module below for reference: Best, AK <ID3.hs> -- | This module is a generic implementation -- of the ID3 decision tree algorithm. -- -- A choice node on a ``continuous'' attribute is -- handled by splitting the population in two via the mean attribute value. module ID3 where import Data.Ord import Data.List import qualified Data.Map as Map data DecisionTree item outcome = Choice (item -> DecisionTree item outcome) | Leaf outcome data Attribute item = Discrete (item -> Integer) | Continuous (item -> Double) runDecisionTree :: DecisionTree item outcome -> item -> outcome runDecisionTree (Leaf outcome) _ = outcome runDecisionTree (Choice f) item = runDecisionTree (f item) item id3 :: (Ord outcome) => [Attribute item] -> [(item, outcome)] -> DecisionTree item outcome -- When there are no unused attributes left, select the most common outcome. id3 [] xs = Leaf $ fst $ head $ sortBy (comparing (negate.snd)) $ histogram (map snd xs) -- When all the items have the same outcome, pick that outcome id3 attrs xs | allEqual (map snd xs) = Leaf $ snd $ head xs -- Otherwise pick the attribute with minimum entropy | otherwise = let (bestAttr:moreAttrs) = sortBy (comparing (informationGain xs)) attrs in case bestAttr of Discrete attr -> let attrTreeMap = Map.fromList attrTrees allAttrValues = nub $ map (attr . fst) xs subtree v = id3 moreAttrs (filter (\(x,_) -> v /= attr x) xs) attrTrees = [(v, subtree v) | v <- allAttrValues] in Choice $ \item -> case Map.lookup (attr item) attrTreeMap of Just subtree -> subtree Nothing -> error "id3: encountered a discrete attribute value that wasn't in the training set" Continuous attr -> let meanv = mean (map (attr.fst) xs) ltTree = id3 moreAttrs (filter (\(x,_) -> attr x < meanv) xs) gtTree = id3 moreAttrs (filter (\(x,_) -> attr x >= meanv) xs) in Choice $ \item -> if attr item < meanv then ltTree else gtTree informationGain :: Ord outcome => [(item, outcome)] -> Attribute item -> Double informationGain xs (Discrete attr) = currentEntropy - sum (map term allAttributeValues) where currentEntropy = entropy (map snd xs) term a = probabilityOf (==a) * entropy (outcomesFor (==a)) probabilityOf f = fromIntegral (length (outcomesFor f)) / fromIntegral (length xs) outcomesFor f = map snd $ filter (f . attr . fst) xs allAttributeValues = nub $ map (attr . fst) xs informationGain xs (Continuous attr) = currentEntropy - term (< meanv) - term (>= meanv) where currentEntropy = entropy (map snd xs) term f = probabilityOf f * entropy (outcomesFor f) probabilityOf f = fromIntegral (length (outcomesFor f)) / fromIntegral (length xs) outcomesFor f = map snd $ filter (f . attr . fst) xs meanv = mean (map (attr.fst) xs) entropy :: Ord a => [a] -> Double entropy xs = sum $ map (\(_,n) -> term (fromIntegral n)) $ histogram xs where term 0 = 0 term n = - (n / num) * log (n / num) / log 2 num = fromIntegral (length xs) histogram :: Ord a => [a] -> [(a, Int)] histogram = buildHistogram Map.empty where buildHistogram map [] = Map.assocs map buildHistogram map (x:xs) = buildHistogram (Map.insertWith (+) x 1 map) xs -- Simple "utility" functions allEqual :: Eq a => [a] -> Bool allEqual = and . mapAdjacent (==) mapAdjacent :: (a -> a -> b) -> [a] -> [b] mapAdjacent f xs = zipWith f xs (tail xs) mean :: (Real a, Fractional n) => [a] -> n mean xs = realToFrac (sum xs) / realToFrac (length xs) -------------------------------------------------------------------- -- Testing Area -------------------------------------------------------------------- data Item = Item String Double Double Bool deriving Show outlook (Item "sunny" _ _ _) = 1 outlook (Item "overcast" _ _ _) = 2 outlook (Item "rain" _ _ _) = 3 temp (Item _ i _ _) = (realToFrac i) / (realToFrac 100) humidity (Item _ _ i _) = (realToFrac i) / (realToFrac 100) windy (Item _ _ _ False) = 0 windy (Item _ _ _ True) = 1 -- attributes a1 = Discrete outlook a2 = Continuous temp a3 = Continuous humidity a4 = Discrete windy outlookData = ["sunny","sunny","overcast","rain","rain","rain","overcast","sunny","sunny","rain","sunny","overcast","overcast","rain"] tempData = [85, 80, 83, 70, 68, 65, 64, 72, 69, 75, 75, 72, 81, 71] humidityData = [85, 90, 78, 96, 80, 70, 65, 95, 70, 80, 70, 90, 75, 80] windyData = [False, True, False, False, False, True, True, False, False, False, True, True, False, True] outcomes = [0,0,1,1,1,0,1,0,1,1,1,1,1,0] accuracy t = naccurate / ntotal where naccurate = fromIntegral $ length $ filter (== True) check ntotal = fromIntegral $ length check check = map (\x -> fst x == snd x) comparison comparison = zip outcomes $ map (runDecisionTree t) items items = zipWith4 Item outlookData tempData humidityData windyData d = zip items outcomes t1 = id3 [a1] d t2 = id3 [a2] d t3 = id3 [a3] d t4 = id3 [a4] d t5 = id3 [a1,a2,a3,a4] d results = map accuracy [t1, t2, t3, t4, t5] </ID3.hs>

3 3

Parsec chapter in realworldhaskell (ch.16)
by Obscaenvs 14 Oct '11

14 Oct '11

In http://book.realworldhaskell.org/read/using-parsec.html , under the heading "Extended example: Full CSV Parser", there is in the function quotedChar an occurrence of the operator <|> with a try after it (i.e. to the right) . Now, in this chapter it says a little before that "|try| only has an effect if it is on the left of a |<|>|.". So in this particular case, try has no effect, or? The offending code: <code>quotedChar = noneOf "\"" <|> try (string "\"\"" >> return '"')</code> Help much appreciated, if not absolutely vital :) /Fredrik

2 1

[Haskell-Beginners] Trouble installing Hoogle.
by Paulo Pocinho 13 Oct '11

13 Oct '11

After cabal install hoogle, it asked me to update the hoogle database. It pulled some files with wget and got stuck afterwards. C:\> hoogle data Extracting tarball... gzip: ..\hackage-cabal.tar.gz: No such file or directory hoogle.exe: System command failed: gzip --decompress --force ..\hackage-cabal.tar.gz Gzip is available from system PATH. How can I fix this?

1 0

Data structure for Propositional Logic formulas
by Alexander Raasch 13 Oct '11

13 Oct '11

Hi, I wrote this program to work with formulas in propositional logic: data Formula = | Variable Char | Not Formula | And Formula Formula | Or Formula Formula | Imply Formula Formula | Equivalent Formula Formula deriving (Eq) instance Show Formula where show (Variable v) = [v] show (Not f) = "~" ++ show f show (And f g) = "(" ++ show f ++ " & " ++ show g ++ ")" show (Or f g) = "(" ++ show f ++ " v " ++ show g ++ ")" show (Imply f g ) = "(" ++ show f ++ " -> " ++ show g ++ ")" show (Equivalent f g ) = "(" ++ show f ++ " <-> " ++ show g ++ ")" To make a formula you can do something like: ghci> let f = Or (Variable 'C') (And (Variable 'A') (Not (Variable 'C'))) ghci> f (C v (A & ~C)) So, my questions are: 1. Do you think this is an elegant solution or would you define custom operators (or, and, ->, <->) instead? Or something completely different? 2. If I pack this code into a module how would add a new logic connective like xor or nand to Formula? Meaning, can I add another type constructor to it? 3. Is there a way to "nest" data definitions, e.g. I would like to replace the 'Variable Char' type constructor by 'Literal Char', whereas a Literal is either a Variable or a negated Variable. Literals can be negated, too. Thanks a lot. Alex

5 7

first open source haskell project and a mystery to boot
by Alia 13 Oct '11

13 Oct '11

Hi folks, Given that I received such excellent help from this newsgroup recently, I wanted to share my first open-source haskell project available here: https://github.com/aliakhouri/newsagent It's a simple command line feed (atom, rss) retriever and analyzer in the early stages of development, using the excellent feed / tagsoup libs to download and analyze feeds from the net. The real intention is to use it as a platform to learn about information retrieval and machine learning techniques in haskell. To this end, I was searching for classification algorithms and I was on the lookout for a nice clear implementation in haskell of canonical decision tree based classification algorithms. My first discovery was an old DecisionTree package on hackage but it's poorly documented and has no examples of usage. So I kept searching... Then I found an hpaste page (http://hpaste.org/steps/11355) which looked at lot more promising, but it also has no example or documentation. In fact, it's an island of code without any references (I don't know who the author is) and nobody has ever referred to it by url or by blog post). It's a mystery to me. In any case, I've tried to create a working example but I'm stuck because you can't mix strings and numbers in a list, and I can't decide whether that's when the author gave up, or whether I've missed the point. Like I said it's a mystery. I would appreciate if anyone could shed some light on this whimsical problem. In case you are wondering why this is relevant to the beginner's forum. Well... firstly, I am a beginner, and, er... the code is short enough to serve pedagogical purposes (-; AK <ID3.hs> -- | This module is a generic implementation -- of the ID3 decision tree algorithm. -- -- A choice node on a ``continuous'' attribute is -- handled by splitting the population in two via the mean attribute value. module ID3 where import Data.Ord import Data.List import qualified Data.Map as Map data DecisionTree item outcome = Choice (item -> DecisionTree item outcome) | Leaf outcome data Attribute item = Discrete (item -> Integer) | Continuous (item -> Double) runDecisionTree :: DecisionTree item outcome -> item -> outcome runDecisionTree (Leaf outcome) _ = outcome runDecisionTree (Choice f) item = runDecisionTree (f item) item id3 :: (Ord outcome) => [Attribute item] -> [(item, outcome)] -> DecisionTree item outcome -- When there are no unused attributes left, select the most common outcome. id3 [] xs = Leaf $ fst $ head $ sortBy (comparing (negate.snd)) $ histogram (map snd xs) -- When all the items have the same outcome, pick that outcome id3 attrs xs | allEqual (map snd xs) = Leaf $ snd $ head xs -- Otherwise pick the attribute with minimum entropy | otherwise = let (bestAttr:moreAttrs) = sortBy (comparing (informationGain xs)) attrs in case bestAttr of Discrete attr -> let attrTreeMap = Map.fromList attrTrees allAttrValues = nub $ map (attr . fst) xs subtree v = id3 moreAttrs (filter (\(x,_) -> v /= attr x) xs) attrTrees = [(v, subtree v) | v <- allAttrValues] in Choice $ \item -> case Map.lookup (attr item) attrTreeMap of Just subtree -> subtree Nothing -> error "id3: encountered a discrete attribute value that wasn't in the training set" Continuous attr -> let meanv = mean (map (attr.fst) xs) ltTree = id3 moreAttrs (filter (\(x,_) -> attr x < meanv) xs) gtTree = id3 moreAttrs (filter (\(x,_) -> attr x >= meanv) xs) in Choice $ \item -> if attr item < meanv then ltTree else gtTree informationGain :: Ord outcome => [(item, outcome)] -> Attribute item -> Double informationGain xs (Discrete attr) = currentEntropy - sum (map term allAttributeValues) where currentEntropy = entropy (map snd xs) term a = probabilityOf (==a) * entropy (outcomesFor (==a)) probabilityOf f = fromIntegral (length (outcomesFor f)) / fromIntegral (length xs) outcomesFor f = map snd $ filter (f . attr . fst) xs allAttributeValues = nub $ map (attr . fst) xs informationGain xs (Continuous attr) = currentEntropy - term (< meanv) - term (>= meanv) where currentEntropy = entropy (map snd xs) term f = probabilityOf f * entropy (outcomesFor f) probabilityOf f = fromIntegral (length (outcomesFor f)) / fromIntegral (length xs) outcomesFor f = map snd $ filter (f . attr . fst) xs meanv = mean (map (attr.fst) xs) entropy :: Ord a => [a] -> Double entropy xs = sum $ map (\(_,n) -> term (fromIntegral n)) $ histogram xs where term 0 = 0 term n = - (n / num) * log (n / num) / log 2 num = fromIntegral (length xs) histogram :: Ord a => [a] -> [(a, Int)] histogram = buildHistogram Map.empty where buildHistogram map [] = Map.assocs map buildHistogram map (x:xs) = buildHistogram (Map.insertWith (+) x 1 map) xs -- Simple "utility" functions allEqual :: Eq a => [a] -> Bool allEqual = and . mapAdjacent (==) mapAdjacent :: (a -> a -> b) -> [a] -> [b] mapAdjacent f xs = zipWith f xs (tail xs) mean :: (Real a, Fractional n) => [a] -> n mean xs = realToFrac (sum xs) / realToFrac (length xs) -------------------------------------------------------------------- -- Testing Area -------------------------------------------------------------------- outlook s | s == "sunny" = 1 | s == "overcast" = 2 | s == "rain" = 3 temp :: (Real a, Fractional n) => a -> n temp i = (realToFrac i) / (realToFrac 100) humidity :: (Real a, Fractional n) => a -> n humidity i = (realToFrac i) / (realToFrac 100) windy x | x == False = 0 | x == True = 1 -- attributes a1 = Discrete outlook a2 = Continuous temp a3 = Continuous humidity a4 = Discrete windy outlookData = ["sunny","sunny","overcast","rain","rain","rain","overcast","sunny","sunny","rain","sunny","overcast","overcast","rain"] tempData = [85, 80, 83, 70, 68, 65, 64, 72, 69, 75, 75, 72, 81, 71] humidityData = [85, 90, 78, 96, 80, 70, 65, 95, 70, 80, 70, 90, 75, 80] windyData = [False, True, False, False, False, True, True, False, False, False, True, True, False, True] outcomes = [0,0,1,1,1,0,1,0,1,1,1,1,1,0] d1 = zip outlookData outcomes d2 = zip tempData outcomes d3 = zip humidityData outcomes d4 = zip windyData outcomes t1 = id3 [a1] d1 t2 = id3 [a2] d2 t3 = id3 [a3] d3 t4 = id3 [a4] d4 --t5 = id3 [a1,a2,a3,a4] [d1,d2,d3,d4] -- doesn't work because you can't mix strings and numbers in a list -- ---------------- </ID3.hs>

3 2

How would you improve this program?
by Lorenzo Bolla 12 Oct '11

12 Oct '11

Hi all, I'm new to Haskell and I'd like you to take a look at one of my programs and tell me how you would improve it (in terms of efficiency, style, and so on!). The source code is here: https://github.com/lbolla/stanford-cs240h/blob/master/lab1/lab1.hs The program is an implementation of this problem: http://www.scs.stanford.edu/11au-cs240h/labs/lab1.html (basically, counting how many times a word appear in a text.) (I'm not a Stanford student, so by helping me out you won't help me to cheat my exam, don't worry!) I've implemented 3 versions of the algorithm: 1. a Haskell version using the standard "sort": read all the words from stdin, sort them and group them. 2. a Haskell version using map: read all the words from stdin, stick each word in a Data.Map incrementing a counter if the word is already present in the map. 3. a Python version using defaultdict. I timed the different versions and the results are here: https://github.com/lbolla/stanford-cs240h/blob/master/lab1/times.png. The python version is the quickest (I stripped out the fancy formatting before benchmarking, so IO is not responsible for the time difference). Any comments on the graph, too? Thanks a lot! L.

6 8

tokenizing a string and parsing the string
by kolli kolli 12 Oct '11

12 Oct '11

Hi, Can anyone help how to tokenize a string and parse it.

4 3

quickCheck generation question
by Joe Van Dyk 11 Oct '11

11 Oct '11

I'm going through the 99 Haskell problems and am trying to write quickCheck properties for each one. -- 3 (find k"th element of a list) element_at xs x = xs !! x prop_3a xs x = (x < length xs && x >= 0) ==> element_at xs (x::Int) == (xs !! x::Int) When I run prop_3a through quickCheck, it gives up, saying that it only passed 1 test. This makes sense, because the random x is going to be larger than the number of elements in the random list in most cases. So what I need to do is write a generator that generates a random list with length larger than a random integer, but I'm not sure how to do that. Thanks! Joe

2 3

help for the lhs2Tex install
by kolli kolli 10 Oct '11

10 Oct '11

hi, when I am trying to install lhs2tex on my machine(windows).I am getting the following error.Can you please me install lhs2tex.... Microsoft Windows [Version 6.1.7601] Copyright (c) 2009 Microsoft Corporation. All rights reserved. C:\Users\namratha>cabal install lhs2Tex Resolving dependencies... [1 of 1] Compiling Main ( C:\Users\namratha\AppData\Local\Temp\lhs2t ex-1.171640\lhs2tex-1.17\Setup.hs, C:\Users\namratha\AppData\Local\Temp\lhs2tex- 1.171640\lhs2tex-1.17\dist\setup\Main.o ) Linking C:\Users\namratha\AppData\Local\Temp\lhs2tex-1.171640\lhs2tex-1.17\dist\ setup\setup.exe ... Configuring lhs2tex-1.17... setup.exe: kpsewhich command not found cabal: Error: some packages failed to install: lhs2tex-1.17 failed during the configure step. The exception was: ExitFailure 1

2 1