- Haskell-Cafe - Haskell.org

Greetings...
by Seth Gordon 01 Oct '06

01 Oct '06

I've finally gotten enough round tuits to learn Haskell, and now that I've done some of the exercises from _The Haskell School of Expression_ and I finally (think I) understand what a monad is, the language is making a lot more sense to me (although my code is not always making so much sense to the compiler :-). My employer (MetaCarta) makes a search engine that can recognize geographic data. My group within MetaCarta is responsible for building the "Geographic Data Module" within our software. To do this, we slurp a heap of geographic and linguistic data from a variety of sources, normalize it, and then use some algorithms (that I'm not allowed to describe) to generate the module. This seems like the sort of task that cries out for a functional-programming approach, and that's what we use, sorta: a lot of the code that I'm responsible for is SQL, with chains of "CREATE TEMP TABLE X AS [insert very complicated query here]", some C++ for the parts that would be very time-consuming or impossible to implement in SQL, and shell scripts to tie everything together. I told my tech lead that I want to try porting some of this code to Haskell in the hope that it would run faster and/or be easier to read. He said I should spend two work days on the project and then be prepared to convince my co-workers that further research in this vein is (or is not) worth doing. So before I embark on day 1 of the project, I thought I should check and see if anyone on this list has used Haskell to munge a ten-million-row database table, and if there are any particular gotchas I should watch out for. adTHANKSvance....

3 3

Re: [Haskell-cafe] smallest double eps
by Chad Scherrer 01 Oct '06

01 Oct '06

Tamas, You might want to read Joachim's post more carefully - he's trying to help you, and I think he makes a good point. -Chad > > Am Freitag, den 29.09.2006, 19:30 -0400 schrieb Tamas K Papp: > > > the smallest positive floating point number x such that 1+x /= x? > > That would be the smallest positive number, woudn't it? > > > > Do you mean the smalles postive number x with 1+x /= 1? > > Hi Joachim, > > Specifically, I would be happy with the smallest Double that makes the > statement true. I need it as a convergence bound for an iterative > algorithm. Anyhow, thanks for the clarification, but I would be > happier with an answer. > > Tamas > > > ------------------------------ > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > End of Haskell-Cafe Digest, Vol 37, Issue 92 > ******************************************** > -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

8 9

cutting long strings into lines
by Andrea Rossato 01 Oct '06

01 Oct '06

Hello! I've been trying for quite some time to find an elegant solution to cut long strings into lines, but the only solution I was able to come up is the following piece of ugly code. Is there a library function for that? What kind of approach would you suggest? Thanks for your kind attention. Andrea Here's the code: -- does the actual job wrapString str = foldr addNL "" $ rmFirstSpace $ concat $ splitS (getIndx $ indx str) str -- gets the indexes of the spaces within a string indx = findIndices (\x -> if x == ' ' then True else False) -- gets the indexes of where to split the string into lines: lines -- must be between 60 and 75 char long getIndx :: [Int] -> [Int] getIndx = takeFirst . checkBound . (delete 0) . nub . map (\x -> if x > 60 && x `rem` 60 >= 0 && x `rem` 70 <= 10 then x else 0) -- groups indexes when their distance is too short checkBound = groupBy (\x y -> if y - x < 10 then True else False) -- takes the first index of a group of indexes takeFirst = map (\(x:xs) -> x) -- split a string given a list of indexes splitS _ [] = [] splitS (x:xs) (ls) = [take x ls] : splitS (map (\i -> i - x) xs) (drop x ls) splitS _ ls = [ls]:[] -- remove the first space from the begging of a string in a list of strings rmFirstSpace = map (\(x:xs) -> if x == ' ' then xs else x:xs) -- used by foldr to fold the list of substrings addNL s s1 = s ++ "\n" ++ s1 try with putStrLn $ wrapString longString where: longString = "The Haskell XML Toolbox (HXT) is a collection of tools for processing XML with Haskell. The core component of the Haskell XML Toolbox is a domain specific language, consisting of a set of combinators, for processing XML trees in a simple and elegant way. The combinator library is based on the concept of arrows. The main component is a validating and namespace aware XML-Parser that supports almost fully the XML 1.0 Standard. Extensions are a validator for RelaxNG and an XPath evaluator."

7 11

Re: [Haskell-cafe] smallest double eps
by Victor Bandur 01 Oct '06

01 Oct '06

-------- Forwarded Message -------- From: Victor Bandur <bandurvp(a)mcmaster.ca> Reply-To: bandurvp(a)mcmaster.ca To: Brandon Moore <brandonm(a)yahoo-inc.com> Subject: Re: [Haskell-cafe] smallest double eps Date: Sat, 30 Sep 2006 20:17:05 -0400 Hi all, I'm new to this mailing list, so my response may be a little out of place, but I think either what's being asked is what is the smallest x such that 1 + x /= 1 (machine epsilon,) or the largest such that 1+x /= x. The bounds seem to be confused. Victor On Sat, 2006-30-09 at 16:10 -0700, Brandon Moore wrote: > Bryan Burgers wrote: > >> >>> Hang on, hang on, now I'm getting confused. > >> >>> First you asked for the smallest (positive) x such that > >> >>> 1+x /= x > >> >>> which is around x=4.5e15. > >> >> > >> >> 1 + 0 /= 0 > >> >> > >> >> 0 is smaller than 4.5e15 > >> >> > >> >> So I don't understand this at all... > >> > > >> > But then 0 isn't positive. > >> > >> Why not? > >> In any case every positive number nust satisfy the above inequation > >> so what > >> about 0.1, which is certainly smaller than 4500000000000000? > People are confusing equality and inequality - > the nontrivial thing here is to find the smallest positive x > that satisfies the equation 1 + x == x. > > In math, every positive number must satisfy the above inequation, that > > is true. But as Chad said, the smallest number in Haskell (at least > > according to my GHC, it could be different with different processors, > > right?) that satisfies the equation is 2.2e-16. > And you've changed the subject - the stuff above was talking about > x + 1 /= x, you're demonstrating solutions to a different problem, > finding the smallest > x such that 1 + x == 1. That's the number often called epsilon. > >> 1 + 2.2e-16 /= 1 > > True > >> 1 + 2.2e-17 /= 1 > > False > Let's stop confusing ourselves about this. > > Brandon > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

cant get trivial c2hs to work
by Anatoly Yakovenko 30 Sep '06

30 Sep '06

I am trying to figure out how to use c2hs, so I wrote a wrapper for asin from math.h: $ cat ASin.chs module MySin (mysin) import C2HS #include "math.h" asin::Double -> Double asin xx = {#call fun asin#} xx and this is my main: $ cat Main.hs module Main where import ASin main = do putStrLn $ show $ asin 0.5 `c2hs ASin.chs` generates this: $ cat ASin.hs -- GENERATED by C->Haskell Compiler, version 0.14.5 Travelling Lightly, 12 Dec 2005 (Haskell) -- Edit the ORIGNAL .chs file instead! {-# LINE 1 "ASin.chs" #-}module MySin (mysin) import C2HS asin::Double -> Double asin xx = asin xx foreign import ccall safe "ASin.h asin" asin :: (CDouble -> CDouble) but, when i try to build the wone thing, i get an error that i dont understand: $ ghc -v --make -fffi Main.hs Glasgow Haskell Compiler, Version 6.4.2, for Haskell 98, compiled by GHC version 6.4.2 Using package config file: /usr/lib/ghc-6.4.2/package.conf Hsc static flags: -static *** Chasing dependencies: Chasing modules from: Main.hs *** Deleting temp files Deleting: ASin.chs:2:0: parse error on input `import' So, what am i missing?

1 1

Is Haskell a 5GL?
by David Curran 30 Sep '06

30 Sep '06

Sorry if this comes across as the rant it is. If you are interested in doing useful stuff rather then navel gazing please stop here. Where are compute languages going? I think multi core, distributed, fault tolerant. So you would end up with a computer of the sort envisioned by Hillis in the 80s with his data parallel programs. The only language that seems even close to this model is Erlang. What am I missing about the ability of Haskell to distribute across processors or a network? Say instead of fault tolerant it is fault avoiding. Can proving programs correct (with Haskell) really reduce our workload? http://www.seas.upenn.edu/~sweirich/wmm/03-benton.pdf Finally is Haskell a language for programming or a mental gymnasium that might be the proving ground for concepts in the next popular language? To quote from a post on the topic "Old functional programming ideas " on programming.reddit.com "Church-Turing equivalence tells us that all models of recursive computing have the same formal power. But it tells us nothing about which models are the most effective way for humans to understand and express definitions of functions. For some reason I'd expect researchers in programming languages to have a lot of opinions on this subject. But they don't seem to talk about it much. Instead, a cynical and mean-spirited person might come to the conclusion that PL researchers (such as Wadler) are actually just mathematicians, who happen to have discovered a new name for their specialty which comes with a lot more funding. They certainly seem quite comfortable working in a notation that almost no programmers understand or seem to be learning. If a responsible scientist wanted to counter this cynical, mean-spirited, and generally Luddite and Philistine argument, what would he or she say?"

6 6

Re: [Haskell-cafe] smallest double eps
by Chad Scherrer 30 Sep '06

30 Sep '06

> > Hang on, hang on, now I'm getting confused. > > First you asked for the smallest (positive) x such that > 1+x /= x > which is around x=4.5e15. > Then Joachim wondered if you wanted > 1+x /= 1 > which is around x=2.2e-16. > But not you claim to be looking for the smallest positive number that > a Double can represent. Which is a totally different beast. The > smallest possible Double depends on if you want to accept > denormalized numbers or not. If you don't, then it's about x=4.5e-308. > > Now what is the number you are looking for? > > -- Lennart > This is the point I was confused about also. Joachim seemed to be correcting what might have been a misstatement of the problem.

1 0

smallest double eps
by Tamas K Papp 30 Sep '06

30 Sep '06

Hi, Is there a built-in constant in Haskell (or, if it is compiler-specific, in ghc) that gives the smallest positive floating point number x such that 1+x /= x? Some languages refer to that as double.eps or similar. I need it for numeric algorithms. Thanks, Tamas

3 4

Optimization problem
by Magnus Jonsson 29 Sep '06

29 Sep '06

Dear Haskell Cafe, When programming the other day I ran into this problem. What I want to do is a function that would work like this: splitStreams::Ord a=>[(a,b)]->[(a,[b])] > splitStreams [(3,x),(1,y),(3,z),(2,w)] [(3,[x,z]),(1,[y]),(2,[w])] I don't care about the order that the pairs are output, so the answer could just as well be [(2,[w],(3,[x,z]),(1,[y])]. However I do care about the order of the xyzw:s, so (3,[z,x]) could not be part of the solution in this example. Furthermore it should work on infinite lists. It can't eat the whole list before producing any output. Now, it's not too hard to come up with an inefficient solution that traverses the input list multiple times. For example a sieving solution: import Data.List splitStreams [] = [] splitStreams ((channel,msg):rest) = let (myMsgs,otherMsgs) = partition (\(c,_)->c==channel) rest in (channel, msg : map snd myMsgs) : splitStreams otherMsgs I'm afraid this algorithm is O(n*m) time in the worst case, where n is the length of the input list, and m is the number of unique channels. But is there any way to write it such that each element is touched only once? Or at least an O(n*log(m)) algorithm? Any takers? / Magnus Jonsson

14 43

Optimizing a title matcher
by Lyle Kopnicky 29 Sep '06

29 Sep '06

Hi folks, I'm competing in a contest at work, and we're allowed to use whatever language we want. I decided this was my chance to prove to people that Haskell was up to the challenge. Unfortunately, I ran into performance problems. Since the contest ends this Friday, I've decided to switch to C++ (gasp!). But if any of you have advice on how to speed up this code, it could help me advocate Haskell in the future. It's supposed to match movie titles from an imported database to a reference database. The version I've sent doesn't do anything very smart - it's just doing literal title matches. The first argument to the program is the filename of the table to be imported, and the second is the filename of the reference table. The first line of each table is a pipe-separated list of field names; the rest of the lines are records, each a pipe-separated list of values. The import files each have 3,000 records, and the reference table has 137,986 records. Building the hash tables out of the files is quick - it just takes a few seconds. But doing the matching of title_id in one table to title_id in the other, in a nested loop between both tables, takes way too long. It's matching two import titles (against each of the reference titles) per second. It needs to do at least 20 per second to qualify for the contest, and it's not doing anything fancy yet. I tried various "improvements" to speed it up. One was to specifically use ByteString, eliminating the AbsString class. Didn't make a difference. Another was to use arrays instead of lists to store each record, and precompute the indices of each of the fields within those records. I also iterated over a list of keys instead of the list of Maps, and only converted each record to a Map one at a time, hoping they would be disposed of sooner. Instead of speeding up the program, this slowed it down by a factor of 20! I've profiled it, and I can't make much out of that. It seemed to be spending 25% of its time doing scoring, and I though the problem must be due to laziness, but I'm not sure. So if anyone has any ideas how to speed this up by a factor of at least 10 times, it would be really appreciated! Even the Ruby solutions are doing that, which is embarrassing. Thanks, Lyle

8 11