- Beginners - Haskell.org

Important coding guideline and library proposal
by Daniel Fischer 23 Nov '09

23 Nov '09

Guideline: NEVER, *never ever*, use 'length' ***unless you really want to know the exact length of a list*** Proposal: rename 'length' to 'yesIReallyWantToKnowTheExactLengthOfThisListSoPleaseCalculateItForMe' to reduce performance bugs caused by naive uses of length.

7 9

Fwd: [Haskell-beginners] combinatorial
by Patrick LeBoutillier 22 Nov '09

22 Nov '09

Forgot to forward my response to the list... ---------- Forwarded message ---------- From: Patrick LeBoutillier <patrick.leboutillier(a)gmail.com> Date: Sun, Nov 22, 2009 at 5:03 PM Subject: Re: [Haskell-beginners] combinatorial To: "Michael P. Mossey" <mpm(a)alumni.caltech.edu> Michael, Here's how I would go about this: type MidiPitch = Int range :: [MidiPitch] range = [10..90] -- Just a dummy eval function, allows up or down one unit eval ps | length ps <= 1 = Just 1.0 eval ps | length ps > 1 = let a = last ps b = last . init $ ps in if abs (a - b) == 1 then Just 1.0 else Nothing coolFunc :: Int -> MidiPitch -> ([MidiPitch] -> Maybe Float) -> [[MidiPitch]] coolFunc n p f = generate n f [[p]] -- Generate MidiPitch lists up to a given length, making sure each step -- satisfies the eval function generate :: Int -> ([MidiPitch] -> Maybe Float) -> [[MidiPitch]] -> [[MidiPitch]] generate n f cs | n == 1 = cs generate n f cs = generate (n-1) f $ concat . map (\p -> try p cs) $ range -- Tries to add a MidiPitch to each of the MidiPitch lists, keep -- only the sequences that pass the eval. try :: MidiPitch -> [[MidiPitch]] -> [[MidiPitch]] try p = filter (not . null) . map (test p) where test p ps = let ps' = ps ++ [p] in case eval ps' of Nothing -> [] otherwise -> ps' It's seems to work, although I'm sure many bits sould be made more elegant... Note: After that another pass would be required over the result set to find the sequences that have the highest scores. Patrick On Sun, Nov 22, 2009 at 5:25 AM, Michael P. Mossey <mpm(a)alumni.caltech.edu> wrote: > I'm trying to write a combinatorial search algorithm with evaluation, and > kind of stuck. Not sure how to do this. > > I'm constructing a musical phrase, which is a list of MidiPitch: > > [MidiPitch] > > I have an evaluation function that determines the fitness of any given > phrase: > > eval :: [MidiPitch] -> Maybe Float > > This returns Nothing if the phrase is completely unacceptable. > > The idea is to build up a phrase one midi pitch at a time, choosing all > possible next pitches (notes) from a range: > > next pitch comes from: [10..90] > > Most of the pitches will result in a phrase that evaluates to Nothing, so > the combinatoral "explosion" will be limited. > > I'd like to write a function that constructs a phrase of length n, and in > fact will have to return a list of all phrases that have equal scores of the > maximum. > > -- <length of output phrase> -> <first pitch> -> <eval func> -> > -- <all tied phrases of best score> > coolFunc :: Int -> MidiPitch -> ([MidiPitch] -> Maybe Float) -> > [[MidiPitch]] > > I am stuck on how to write this. > > thanks, > Mike > > > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners > -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

1 0

Performance
by Philip Scott 22 Nov '09

22 Nov '09

Hi again folks, I am still at it with my time-series problem, for those who haven't been following; I have a list of (time stamp, value) pairs and I need to do various bits and bobs with them. I have got arithmetic down pat now, thanks to the kind help of various members of the list - now I am looking at functions that look at some historical data in the time-series and do some work on that to give me an answer for a particular day. I have chosen to represent my time series in reverse date order, since non of the operations will ever want to look into the future, but often they would like to look in to the past. A function I would like to write is 'avg'. For a particular day, it computes the average of the values last 'n' points; if there are not n points to fetch, thee is no answer. I then combine those to make a new time series. e.g. If my input time series was [(5,10),(4,20),(3,30),(2,40), (1,50)] (Where 5, 4, 3, 2, 1 are timestamps and 10, 20, 30, 50, 50 are values) I would like the answer [(5,20), (4,30), (3,40)] (e.g. 20 = (10+20+30)/3 etc.. I can't get an answer for timestamps 2 and 1 because there isn't enough historical data) So I have written some code to do this, and it works nicely enough; but it is _slow_. To do 1000 averages of different lengths on a series with only 3000 points takes about 200 seconds on my (not overly shabby) laptop. The equivalent C program takes under a second. I am entirely sure that this is due to some failing on my part. I have been mucking around with the profiler all afternoon lazifying and delazifying various bits and bobs with no dramatic success so I thought I might put it to y'all if you don't mind! So here's some code. I've kept it quite general because there are a lot of functions I would like to implement that do similar things with bits of historical data. General comments on the Haskellyness/goodness of my code are welcomed as well, I'm still very much a beginner at this! --------- SNIP -------------- -- Take n elements from a list if at least n exist takeMaybe n l | length l < n = Nothing | otherwise = Just $! (take n l) -- Little utility function, take a function f and apply it to the whole list, -- then the tail etc... lMap _ [] = [] lMap f (x:xs) = (f (x:xs)):(lMap f xs) -- Little utility function to take a list containing Maybes and delete them -- Returning a list with the values inside the Just maybeListToList [] = [] maybeListToList (x:xs) = maybe (maybeListToList xs) (\y -> y:(maybeListToList xs)) x -- Return a list of lists, where each sublist is a list of the next n values histMaybe x = lMap (takeMaybe x) hist n x = maybeListToList $ histMaybe n x -- Take a function which works on a list of things and apply it only to a -- list of the second elements in a list of tuples 'l'. applyToValues f l = let (ts,vs) = unzip l in zip ts $ f vs -- Create a timeseries with the cumulative sum of the last n values cumL n l = map sum (hist n l) cum = applyToValues . cumL -- Creates a timeseries with the average of the last n values avgL n l = map ((*) (1/fromIntegral(n))) $ cumL n l avg = applyToValues . avgL --------- SNIP -------------- According to the profiler (log attached), the vast majority of the time is spent in takeMaybe, presumably allocating and deallocating enormous amounts of memory for each of my little temporary sublists. I have tried liberally sprinkling $! and 'seq' about, thinking that might help but I am clearly not doing it right. Perhaps list is the wrong basic data structure for what I am doing? I hope I didn't bore you with that rather long email, I will leave it at that. If it would be useful, I could give you the complete program with a data set if anyone is keen enough to try for themselves. Thanks, Philip

3 2

Type classes and synonyms
by Philip Scott 22 Nov '09

22 Nov '09

Hello all, Quick one for you. I have a list of (<timestamp>,<value>) pairs, and I have defined lots of nice functions for doing various tricks with them. I'd like to define a custom data type which is an instance of 'Num' so I can conveniently do arithmetic on them. (I have written some tools for merging two time series etc...) e.g. t (x,y) = x v (x,y) = y mergeSkip _ [] = [] mergeSkip [] _ = [] mergeSkip (x:xs) (y:ys) | t x == t y = ( t x, (v x, v y) ) : (mergeSkip xs ys) | t x > t y = mergeSkip xs (y:ys) | t x < t y = mergeSkip (x:xs) ys binaryValueFunc f [] = [] binaryValueFunc f ((t,(a,b)):xs) = (t, f a b):binaryValueFunc f xs add xs = binaryValueFunc (+) xs addSkip xs ys = add $ mergeSkip xs ys So addSkip will nicely take two of my time series, merge them by throwing out any pairs which don't have a time stamp that exists in both and then add the values to return a new series. All is well. But how do I make it so that I can use the + operator to add two of them? Well of course, I tried making a custom data type: data Ts a b = Ts [(a,b)] intance Ts Num where <blaa blaa blaa> But then I have to rewrite all of my functions to pattern match on Ts instead of just the list. Worse, when I am writing recursive functions I have to construct a Ts again for the recursive call. I guess I could make my own 'list-like' datastructure data Ts a b = Empty | Cons ((a,b), Ts) But that seems rather clumsy. So I tried to make 'Ts' a type synonym for [(a,b)] which worked, but then I couldn't declare it an instance of 'Num'. So I guess the question is, is there any way of making a type synonym for a type which I can define as an instance of another class? So I can use my values of the type synonym for functions which expect the 'vanilla' type, but define 'extra' stuff my type synonym can do? Any help or advice greatly appreciated. - Philip

12 30

Show how the evaluation works
by John Moore 22 Nov '09

22 Nov '09

Hi All, I'm trying to work out how to show the steps in evaluating "How the function is calculated". In other words I want this program to actually print out the steps. For e.g. eval (Multiply(Add(Val 10) (Val 20)) (Val 3) Which is add 10+20 and multiply by 3 = 90 The program then produces( Prints out) something like working: eval (Multiply(Add(Val 10) (Val 20)) (Val 3) working Add(Val10) (Val 20) answer 1 Val 30 answer 2 Val 90 This is what I have so far but it wont even do the calculations. Any help appreciated. data Expression = Val Float | Add Expression Expression | Subtract Expression Expression | Multiply Expression Expression | Divide Expression Expression deriving Show eval :: Expression -> Float eval (Val x) = x eval (Add x y) = eval x + eval y eval (Multiply x y) = eval x * eval y eval (Subtract x y) = eval x - eval y eval (Divide x y) = eval x / eval y John

3 2

reverse flow .
by Michael P. Mossey 22 Nov '09

22 Nov '09

Can I get some recommendations on defining a function composition operator that flows in the reverse direction? Thanks, Mike

4 3

Is Haskell for me?
by Luis P. Mendes 21 Nov '09

21 Nov '09

Hi, I'd like to have some points of view on this subject. I need to start a project on neural analysis and genetic algorithms that will process many millions of records in a Linux X86_64 box (some development also in a X32 computer). Maybe I'll use fuzzy logic, or case-based reasoning, or decision trees, too. Recently, I finished a small project on genetic algorithms with Python, but since run-time is very important, my next project will need a fast language. Either I'll go to C++ or similar language or I'll try a functiional language - Haskell. Apart from some features in Python, I've never programmed thinking in a functional way. I'd like to avoid having to learn C++. I'd like to concentrate in getting the work done and Haskell seems like a solution. But... My questions are: - Is Haskell able to read (also write to a point) data from databases in a fast and reliable way? (MySql or PostgreSQL) - how could I program something like this in Haskell: .. generate random population .. for each one of the population: .. for time period 1 to ten million: .. evaluate method 1, 2, 3, 4, 5, 6, .... ..evaluate fitness of each one .. generate new population based on results of previous generation It seems relatively intuitive for me to program this in an imperative language. But what about in Haskell? - Is Haskell suitable to process data like this in a fast way (aproximate to C++?) - In order for Haskell to be fast, coding is done in a 'natural' way or with use of special hidden details of the language? - Although I always liked math, I no longer have the knowledge I used to have several years ago. Is this important to help program in this funcional language? - Are there graphical packages available to plot results or is it easy to connect it to a Python (or C) library? - Is code easily reusable in different future projects? Since it has no objects... how can it be done? Sorry for all these questions, but I really need to know about this and that's why I want to read answers from knowledgeable people. Luis

15 17

Re: [Haskell-beginners] Re: Is Haskell for me?
by Nathan M. Holden 21 Nov '09

21 Nov '09

I'm not a Haskell expert-- in fact, I'm a beginner, and that's why I'm here, but I read your blog post on the subject of this hash table program, and it seems to me from reading the comments in reply that you're just here trolling, because you're using an algorithm that is fundamentally not purely functional, and of course that's going to be slower, just like asking Joel Zumaya to pitch left handed. If you were being honest about your complaint, you'd make an apples-to-apples comparison, and a number of commenters on your blog have proposed implementations that perform much better than your example. Sorry if I'm just being a jerk, Nathan M. Holden, Haskell Beginner On Saturday 21 November 2009 12:55:03 pm beginners-request(a)haskell.org wrote: > Message: 4 > Date: Sat, 21 Nov 2009 18:02:33 +0000 > From: Jon Harrop <jon(a)ffconsultancy.com> > Subject: Re: [Haskell-beginners] Re: Is Haskell for me? > To: Ben Lippmeier <ben.lippmeier(a)anu.edu.au> > Cc: beginners <beginners(a)haskell.org> > Message-ID: <200911211802.33494.jon(a)ffconsultancy.com> > Content-Type: text/plain; charset="iso-8859-1" > > On Saturday 21 November 2009 11:56:09 Ben Lippmeier wrote: > > Hmm. I'd be careful about conflating algorithmic complexity with memory > > management issues. > > No need. Just look at how badly the performance scales for Haskell vs other > languages. For example, inserting 1-16 million floating point key/values > into a hash table: > > Haskell OCaml F# > 1M: 3.198s 1.0x 1.129s 1.0x 0.080s 1.0x > 2M: 8.498s 2.7x 2.313s 2.0x 0.138s 1.7x > 4M: 25.697s 8.0x 4.567s 4.0x 0.281s 3.5x > 8M: 97.994s 30.6x 10.450s 9.3x 0.637s 8.0x > 16M: 388.080s 121.4x 23.261s 20.6x 1.338s 16.7x > > Note that Haskell is 290x slower than F# on that last test. > > In practice, you would turn to a purely functional dictionary in Haskell > based upon balanced binary trees in order to work around this > long-standing bug in the GC but those trees incur O(log n) indirections > and typically run orders of magnitude slower than a decent hash table. > > Suffice to say, Haskell is nowhere near being in the ballpark of C++'s > performance for basic functionality like dictionaries and sorting. > > > By the above reasoning, if I were to run any program > > using arrays on a system with a two space garbage collector (which copies > > all live objects during each GC) I could say the worst case algorithmic > > complexity was O(n). That doesn't sound right. > > Can you write a program that demonstrates this effect as I did? > > > I could take this further and say that in a virtual memory system, there > > is a chance that the whole heap gets copied to the disk and back between > > each array update. > > Can you write a program that demonstrates this effect as I did?

2 1

points-free problem
by I. J. Kennedy 20 Nov '09

20 Nov '09

I know I'm going to kick myself when the answer is revealed by one of you kind folks, but after staring at this a while I just can't figure out what's going on. The compiler (ghci) is trying so hard to tell me what's wrong, but I am failing to understand. I thought for the most part one could take a function definition like f x = (blah blah blah) x and turn it into points-free style by f = (blah blah blah) But from the dialog below, my assumption is incorrect. Help? I. J. Kennedy > sortBy (compare `on` fst) [(2,3),(0,1),(1,5)] -- test a little sort expression [(0,1),(1,5),(2,3)] > let sortpairs xss = sortBy (compare `on` fst) xss -- make it into a function > :t sortpairs sortpairs :: (Ord a) => [(a, b)] -> [(a, b)] > sortpairs [(2,3),(0,1),(1,5)] [(0,1),(1,5),(2,3)] > let sortpairs = sortBy (compare `on` fst) -- points-free style > sortpairs [(2,3),(0,1),(1,5)] <interactive>:1:24: No instance for (Num ()) arising from the literal `1' at <interactive>:1:24 Possible fix: add an instance declaration for (Num ()) In the expression: 1 In the expression: (1, 5) In the first argument of `sortpairs', namely `[(2, 3), (0, 1), (1, 5)]' > :t sortpairs sortpairs :: [((), b)] -> [((), b)] -- what?!

3 3

Windows API and FFI
by iæfai 20 Nov '09

20 Nov '09

I have a specific function that I would like to get info to allow me to accept clicks into the cmd.exe window. The function seems to be here: http://msdn.microsoft.com/en-us/library/ms684961(VS.85).aspx One of the parameters is this: A pointer to an array of INPUT_RECORD structures that receives the input buffer data. The total size of the array required will be less than 64K. There are in and out parameters for this function. I have never done anything like this before, and was hoping this is done somewhere, or it is fairly easy to do. Any help would be appreciated. - iæfai.

2 1