November 2009 - Beginners

type classes, java interfaces in type systems space
by John Li 06 Nov '09

06 Nov '09

Hi all, I've been trying to get a feel for the space of programming languages, and in particular, different sorts of type systems. In hopes of clarifying and correcting my thoughts, please bear with me while I ramble for a while, and correct and direct me towards enlightening resources. Abstraction is good, boilerplate is bad, and we'd like to write general code that works for different "sorts" of things. Parametric polymorphism and interfaces are 2 common ways to do this, and fit together well with current strong, static type systems. Parametric polymorphism enables abstraction by allowing functions to operate on a particular "containing" type, but arbitrary "contained" types, exemplified by the many well-known list functions. Abstraction is achieved because the desired functionality only depends on the specific structure (interface?) of the "outer" type. This is essentially exactly what generics in Java are. Interfaces (I use the term in the Java sense, though I'm not fully comfortable with the details) allow one to write code that works with any type, as long as that type provides the functionality specified in an interface. So, type classes in Haskell provide similar functionality to interfaces in Java. It seems like parametric polymorphism is a more restricted case of type classes. Map could perhaps be something like: map :: (Consable xs x, Consable ys y) => (x -> y) -> xs -> ys class Consable xs x where cons :: (x, xs) -> xs decons :: xs -> (x, xs) (I think functional dependencies could be used to link xs and x in the type system?) The Functor class seems similar, but I'm not sure if I see that it's exactly the same. Clojure's "seq" abstraction (implemented for most (all?) of its built-in collection types as well as Java Iterables, etc.) requires "first", "rest", and "cons". Through this interface, Clojure implements map, filter, reverse, etc. once, but they work for all its collections. Thanks for your patience! -John

1 0

Thank you, everyone
by Jordan Cooper 06 Nov '09

06 Nov '09

Just thought I'd give props to everyone on this list -- both askers and answerers. It's been quite helpful for me to read everything, even when I'm not dealing with the same issues. Every online community should strive to be as considerate, intelligent, and all-around helpful as this one. Have a happy weekend!

1 0

Lazy file IO & Space leaks/waste
by Aleksandar Dimitrov 06 Nov '09

06 Nov '09

Hello list, I'm currently writing a small linguistic corpus analyzer. My input file is only 25MB, but profiling shows that the overall amount of allocation over the program's runtime is several GB. That's a little too much - adding to that is the fact that the program is abysmally slow, so I'm suspecting a space leak somewhere. I'm using the ByteString.Lazy.Char8 class in order to work efficiently with lazy IO and I must admit that I'm very inexperienced with predicting runtime and space behaviour of lazy IO :-( It worked well in the past, but I'm stuck now. The program can be found here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=11863#a11863 The important bits are as follows: > mf :: [C.ByteString] -> StdWord > mf [] = Word [] C.empty > mf s = Word (tail s) (head s) > > f' = mf . reverse . C.words > main :: IO () > main = do > corpus_name <- liftM head getArgs > corpus <- liftM (Corpus . (map f') . C.lines) $ C.readFile corpus_name > print $ length (content corpus) > let interesting = filterForInterestingTags interestingTags corpus > print $ show (freqMap interesting) freqMap also uses foldr' to fold the corpus it is given into a Data.Map, but according to the profiling output, that's not where the bad stuff happens. Here's the interesting parts of the profiling output: > analyse +RTS -p -RTS corpus/bnc-samp.tt > > total time = 30.46 secs (1523 ticks @ 20 ms) > total alloc = 14,871,619,904 bytes (excludes profiling overheads) > > COST CENTRE MODULE no. entries %time %alloc %time %alloc > > MAIN MAIN 1 0 0.0 0.0 100.0 100.0 > main Main 221 0 0.0 0.0 0.0 0.0 > CAF Main 206 14 0.1 0.1 100.0 100.0 > showsPrec_aSF Main 223 1 0.0 0.0 0.0 0.0 > interestingTags Main 218 1 0.0 0.0 0.0 0.0 > f' Main 216 1 0.0 0.0 0.0 0.0 > mf Main 217 1 0.0 0.0 0.0 0.0 > main Main 212 1 2.4 4.4 99.9 99.9 > f' Main 219 0 89.0 91.5 90.2 92.7 > mf Main 220 2427450 1.2 1.2 1.2 1.2 > filterForInterestingTags Main 215 1 5.4 0.1 5.4 0.1 > freqMap Main 214 1 0.6 0.5 2.0 2.7 > compare_aRL Main 222 1141996 1.4 2.2 1.4 2.2 Obviously the main cost centre seems to be f' (which I've factored out in order to view it separately as a cost centre.) It's not the call to reverse that makes it slow (removing it doesn't affect the run time.) Interestingly, it prints out the first statement (length) very quickly, then takes a lot of time. I've removed the call to freqMap, and it seems that GHC is smart enough to drop the call to f' completely, because only the length ever gets evaluated. But the freqMap also needs the processing from f', and that's where the bad stuff starts happening. Should I look into DeepSeq? I've tried adding strictness to the functions by hand, and also to the data structures, but that didn't seem to help so far. So I'm looking for solutions to make this faster. I'm guessing that a smart `seq` somewhere might help, but I don't know where :-\ As a side note: how can I find out how the run-time data structures look like in memory? I.e. I want to know *what* exactly stays around as thunks in memory so that I can focus better on where to add strictness or redirect the program flow. Ideally, only a very smart part of the file should ever be in memory, with processing happening incrementally! Thanks for any pointers! Aleks

3 2

N-ary tree search problems
by Ryan Temple 06 Nov '09

06 Nov '09

I'm making a general purpose N-ary tree and im coming up with "unexpected '=' on line 17" as an error. I have spent a fair while trying to work out why this isn't accepting the case that an Empty gtree returns false for any member search. i realise this is probably a very trivial error but any help would be appreciated: module GTrees where data Gtree = Empty | Leaf String | Node String [Gtree] deriving (Show) --Tests if a given string is a member of the tree gtreeMember :: (Ord a) => a -> Gtree a -> Bool gtreeMember y Empty = False -- line 17 gtreeMember y (Leaf x) = (x==y) gtreeMember y (Node x tree) |x==y = True |otherwise gtreeMember tree This is the code up to the point of the error with the error line highlighted

4 3

re: [Haskell-beginners] Show Floats
by Nathan M. Holden 06 Nov '09

06 Nov '09

Um... well, I solved my own problem. It turns out that my 20-30 minutes of searching for a way to \definecolor in terms of 0-255 instead of 0.0-1.0 were just 5 minutes short of finding out a way to do it. This is embarrassing.

3 2

Show Floats
by Nathan M. Holden 06 Nov '09

06 Nov '09

I have been working on a small library that will typeset notes in LaTeX for me, since I tend to have haphazard typesetting while I write, but while I read I like to have standards. Anyways, I defined a datatype data Color = RGB { name :: [Char], r :: Float, g :: Float, b :: Float, matchText :: [[Char]], targetText :: [Char]} deriving(Show,Eq,Read) I wanted to be able to have a piece of code that said "\\definecolor{"++name++"}{rgb}{"++show r++","++show g++","++show b++"}" but because I have numbers below 0.1, it outputs as 2.0e-2, which is useless. I wrote a function that would output useful numbers, but it's REALLY bad Haskell: fToInt :: Float -> Int fToInt f = if f >= 10 then fToInt (f-10.0) else if (f >= 9) then 9 else if (f >= 8) then 8 else if (f >= 7) then 7 else if (f >= 6) then 6 else if (f >= 5) then 5 else if (f >= 4) then 4 else if (f >= 3) then 3 else if (f >= 2) then 2 else if (f >= 1) then 1 else 0 It takes up 11 lines in a module that's only got 74! (128 if you count the module to translate the notes into a .tex file) how would I write this better?

2 1

Does System.Directory work on Windows XP?
by Patrick Larrivee-Woods 04 Nov '09

04 Nov '09

Hi, I"m having trouble getting the System.Directory module in ghci on a Windows XP machine. Whenever I call a function like getCurrentDirectory or getDirectoryContents I get no results back. I was wondering if anyone knows why this is happening, or if someone can point me to a module that works on Windows. Here's an example of what I get: ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.4.2, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base-1.0 ... linking ... done. Prelude> :module System.Directory Prelude System.Directory> getCurrentDirectory Prelude System.Directory> getDirectoryContents "." Prelude System.Directory> getDirectoryContents "c:\\perl" Prelude System.Directory>

3 3

I have created an ugly Haskell program..
by Philip Scott 04 Nov '09

04 Nov '09

.. and I am positive there must be a way of beautifying it, but I am struggling. I bet there is just some lovely way of making this all shrink to three lines.. So here's the problem. I have two lists of tuples: (timestamp, value) What I would like to do in do a kind of 'zip' on two of these lists to make a list of (timestamp, (value1, value2)) with the following rules: - If the timestamps are equal it's easy - make your new element an move on - If one of the lists has a timestamp that the other doesn't, repeat an old value from the other list - If we don't have an old value yet, then don't create an element in the new list. e.g. if I ran my algorithm on these two lists d1 = [ (1,"a"), (2,"b"), (3,"c") ] d2 = [ (2,"b'"), (4,"d'") ] I would like to get result = [ (2, (b,b')), (3, (c,b')), (4, (c,d')) ] e.g. there was no data in d2 for our first element so we skipped it. Okay, so here is my code.. It works, but makes me feel a bit dirty. To explain my nomenclature 't' is 'timestamp of', 'v' is 'value of'. vx' and vy' are the 'old' values from the previous iteration in case a repeat is needed. They are Maybes because at the beginning there may be no old value. d1 = [ (1,"a"), (2,"b"), (3,"c") ] d2 = [ (2,"b'"), (4,"d'") ] t (x,y) = x v (x,y) = y js vx' vy' (x:xs) (y:ys) | t x == t y = ( (t x), (v x, v y) ) : js (Just (v x)) (Just (v y)) xs ys | t x < t y = maybe (js (Just (v x)) Nothing xs (y:ys)) (\z -> ( t x, (v x, z ) ) : ( js (Just (v x)) (Just z) xs (y:ys))) vy' | t x > t y = maybe (js Nothing (Just (v y)) (x:xs) ys) (\z -> ( t y, (z, v y ) ) : ( js (Just z) (Just (v y)) (x:xs) ys)) vx' js vx' vy' (x:xs) [] = maybe [] (\z -> ( t x, (v x, z ) ) : ( js (Just (v x)) (Just z) xs [])) vy' js vx' vy' [] (y:ys) = maybe [] (\z -> ( t y, (z, v y ) ) : ( js (Just z) (Just (v y)) [] ys )) vx' js _ _ [] [] = [] You call it with the first two arguments as Nothing to kick it off (I have a trivial wrapper function to do this) It works fine: > :t js js :: (Ord t) => Maybe a1 -> Maybe a -> [(t, a1)] -> [(t, a)] -> [(t, (a1, a))] > js Nothing Nothing d1 d2 [(2,("b","b'")),(3,("c","b'")),(4,("c","d'"))] But it just feels gross. Any advice on how to tame this beast would be greatly appreciated :) All the best, Philip

4 6

order of monad transformers
by Michael Mossey 04 Nov '09

04 Nov '09

How does one consider the best ordering of monad transformers? For example, if I'm combining ErrorT, StateT (or State), and WriterT (or Writer)? But not just this specific example---what principles can one consult to determine ordering? Thanks, Mike

3 4

about model checking of haskell program
by Liu Jian 02 Nov '09

02 Nov '09

Dear, Is there any work about "model checking haskell program"? in my opinion, think the haskell as a specification language, then we can check it or transform it to other specification language (such as, promela), so can be analyzed. cheers, Liu Jian ---- email to: gjk.liu(a)gmail.com

1 0