- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Re: sizeFM type
by S. Alexander Jacobson 27 Apr '04

27 Apr '04

On Tue, 27 Apr 2004, Tomasz Zielonka wrote: > The data you provided is interesting. However, if I had such a machine, > my work could be much less challenging :) I would note that people today are making strenuous efforts to retain compatibility with a Haskell98 standard that it only 6 years old! If we are making choices intended to have a lifetime of e.g. 10 years (see <http://www.joelonsoftware.com/articles/fog0000000017.html>), then I would observe that the 24gb machine I specced out will, assuming Moore's law lasts, cost only $2k in 5-6 years. The Sun Fire 15k with 288GB of memory and 72 Sparcs (think GPH!), that today costs $2.6m will cost only $155k. Note, since you don't need 72 CPUs, you'll probably be able to get this machine for <$50k. So, perhaps the question here is: What is the planned lifetime of sizeFM? Do we prefer the safety of knowing our code will work at arbitrary scale or the ecstacy of having it run fast today? Put differently, would you rather cope with hardware limitations today or software limitations tomorrow? -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com

1 0

Re: [Haskell] Re: sizeFM type
by Ketil Malde 27 Apr '04

27 Apr '04

[Moved to -cafe at SPJ's request] "Serge D. Mechveliani" <mechvel(a)botik.ru> writes: > On Mon, Apr 26, 2004 at 10:09:18PM +0200, Ketil Malde wrote: >> "Serge D. Mechveliani" <mechvel(a)botik.ru> writes: >>> length :: [a] -> Integer >>> smallLength :: [a] -> Int >> Hmm...isn't it possible to use a class here? Perhaps even Num? > I think, for many functions, like length, it is most natural to > return Integer only. Well, perhaps Integral is a better choice. I was perhaps thinking of functions like: average xs = sum xs / length xs I'd rather have a polymorphic "length", than different versions for each possible return type. One problem could be that with average xs = sum xs / fromIntegral (length xs) the return type of length becomes ambigous? -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

Data constructors
by Mark Carroll 26 Apr '04

26 Apr '04

I keep running into annoyance in having to name data constructors differently if they're for different types if they're in the same module or something. I wish that something like some Type.Constructor syntax worked in order to disambiguate. Or, better still, I have that problem with function names too (e.g. Data.List.union, Data.Set.union, IIRC) and it occurs to me that a lot of this can be resolved automatically because the types only make sense with one of the choices. I'm not really proposing any changes; more, I'm wondering what others' thinking is about this sort of thing - what annoys them, how they get around it, etc. -- Mark

4 4

Hierarchical Library
by haskell＠alias.spaceandtime.org 24 Apr '04

24 Apr '04

Hello, Why does this fail? ========================== import System.Posix test = Temp.mkstemp ========================== Are the libraries hierarchical in name only? Thanks, James

2 2

FiniteMap, Map, FiniteSet, Set
by haskell＠alias.spaceandtime.org 24 Apr '04

24 Apr '04

Here's a really elementary question: Why does the library have [FiniteMap and Set] instead of [FiniteMap and FiniteSet] or just [Map and Set]? Is there some reason for this inconsistency? Thanks, James

3 2

Syntax for modifying nested product types
by Mark Carroll 23 Apr '04

23 Apr '04

I have data objects where each component is a labelled field through which I access or modify it. I have a hierarchy of these - many of the fields are themselves such data objects, so I may need to apply a few selector functions to get down to what I want (call these "deep"). For fairly flat things, the updates using field labels are okay. However, when I have a function that needs to tweak various bits of various "deep" fields, based on various conditions, then it gets really ugly, not least because of the conditions: foo { bar = baz } becomes, let old = bar foo in foo { bar = if cond then f old else old } or whatever. Do I need such a let for each component and sub-component of the object that has a child that may be modified, or will foo { bar = if cond then f (bar foo) else bar foo } be suitably optimised? (The if's inside the {} because there may be multiple fields (or children thereof) being modified based on different conditions.) -- Mark

6 5

Re: [Haskell-cafe] Splitting a list
by Steve Schafer 23 Apr '04

23 Apr '04

On Wed, 21 Apr 2004 14:57:57 +0100, you wrote: >How about implementing a directly recursive solution? Simply >accumulate the sum so far, together with the list elements you have >already peeled off. Once the sum plus the next element would exceed >the threshold, emit the accumulated elements, and reset the sum >to zero. > > splitlist threshold xs = split 0 [] xs > where > split n acc [] = reverse acc: [] > split n acc (x:xs) > | x >= threshold = error (show x++" exceeds threshold ") > | n+x > threshold = reverse acc : split 0 [] (x:xs) > | otherwise = split (n+x) (x:acc) xs Thanks. Apart from a small off-by-one problem (the "x >= threshold" test needs to be "x > threshold" instead), it works fine. I had actually started along those lines, but got bogged down in the details of passing the accumulator around, and ended up painting myself into a corner, so I abandoned that approach (prematurely, as it turns out). And thanks to everyone else who replied--I don't want to clutter the list with a lot of individual replies. As you can probably tell, I've only recently begun playing with Haskell, and the process of reconfiguring my neurons into recursive loops has not yet been completed. -Steve

1 0

Re: [Haskell-cafe] Syntax for modifying nested product types
by MR K P SCHUPKE 23 Apr '04

23 Apr '04

I would just do: f' = if cond0 then f else id g' = if cond1 then g else id foo { bar = f' (bar foo) , wib = g' (wib foo) } I like seeing the record updated, rather than hiding it in a function. Regards, Keean.

1 0

Splitting a list
by Steve Schafer 22 Apr '04

22 Apr '04

I have a list of integers, e.g.: [1,5,3,17,8,9] I want to split it into a pair of lists, with the criterion being that the sum of the elements in the first list is as large as possible, but not exceeding a threshold value. For example, if the threshold is 10, the result should be: ([1,5,3],[17,8,9]) and then I want to recursively apply this process to the remainder of the list, with the end result being a list of lists of integers. Using the same list along with a threshold of 18, I would get: [[1,5,3],[17],[8,9]] I have devised a means of doing this: 1) Create an auxiliary list of integers, where the n'th element is equal to the sum of the first n elements of the original list. 2) Zip the auxiliary list with the original list. 3) Use span to break the list in two according to the threshold. 4) Unzip the two resulting lists and discard the auxiliary portions. 5) Repeat from step 1, operating on the tail of the list, until there's nothing left. Here's the code that implements this: runningSum :: (Ord a, Num a) => [a] -> [a] runningSum [] = [] runningSum (i:[]) = i : [] runningSum (i:j:js) = i : runningSum (i+j : js) zipWithSum :: (Ord a, Num a) => [a] -> [(a,a)] zipWithSum xs = zip (runningSum xs) xs threshold :: (Ord a, Num a) => [a] -> a -> ([(a,a)],[(a,a)]) threshold xs t = let test x = (t >= (fst x)) in span test (zipWithSum xs) splitFirst :: (Ord a, Num a) => [a] -> a -> ([a],[a]) splitFirst xs t = let (ys,zs) = threshold xs t in (snd (unzip ys), snd (unzip zs)) splitAll :: (Ord a, Num a) => [a] -> a -> [[a]] splitAll [] _ = [] splitAll xs t = let (ys, zs) = splitFirst xs t in ys : (splitAll zs t) (One thing that's missing from this code is a check to verify that no single element in the list is greater than the threshold, which should raise an error, rather than get stuck in an infinite loop.) The algorithm as implemented works fine, but it seems overly complicated and not very elegant. I get the feeling that I'm missing some obvious simplification, but I can't find it. Any ideas? Thanks, -Steve Schafer

5 5

Re: [Haskell-cafe] Splitting a list (Modified by Doaitse Swierstra)
by Doaitse Swierstra 21 Apr '04

21 Apr '04

I have the impression that my posting did not make it, so I am trying again: How about: splitList weight l = munch l weight where munch [] _ = [[]] munch p@(x:xs) w = if w >= x then let (r:rr) = munch xs (w-x) in (x:r):rr else []:munch p weight main = print (splitList 18 [1,5,3,17,8,9]) Doaitse Swierstra PS: note that your problem is a bit underspecified: -- what to return for an empty list -- what to do if a number is larger than the weight On 2004 apr 21, at 15:42, Steve Schafer wrote: > I have a list of integers, e.g.: > > [1,5,3,17,8,9] > > I want to split it into a pair of lists, with the criterion being that > the sum of the elements in the first list is as large as possible, but > not exceeding a threshold value. For example, if the threshold is 10, > the result should be: > > ([1,5,3],[17,8,9]) > > and then I want to recursively apply this process to the remainder of > the list, with the end result being a list of lists of integers. Using > the same list along with a threshold of 18, I would get: > > [[1,5,3],[17],[8,9]] > > I have devised a means of doing this: > > 1) Create an auxiliary list of integers, where the n'th element is > equal > to the sum of the first n elements of the original list. > > 2) Zip the auxiliary list with the original list. > > 3) Use span to break the list in two according to the threshold. > > 4) Unzip the two resulting lists and discard the auxiliary portions. > > 5) Repeat from step 1, operating on the tail of the list, until there's > nothing left. > > Here's the code that implements this: > > runningSum :: (Ord a, Num a) => [a] -> [a] > runningSum [] = [] > runningSum (i:[]) = i : [] > runningSum (i:j:js) = i : runningSum (i+j : js) > > zipWithSum :: (Ord a, Num a) => [a] -> [(a,a)] > zipWithSum xs = zip (runningSum xs) xs > > threshold :: (Ord a, Num a) => [a] -> a -> > ([(a,a)],[(a,a)]) > threshold xs t = let test x = (t >= (fst x)) > in span test (zipWithSum xs) > > splitFirst :: (Ord a, Num a) => [a] -> a -> ([a],[a]) > splitFirst xs t = let (ys,zs) = threshold xs t > in (snd (unzip ys), snd (unzip zs)) > > splitAll :: (Ord a, Num a) => [a] -> a -> [[a]] > splitAll [] _ = [] > splitAll xs t = let (ys, zs) = splitFirst xs t > in ys : (splitAll zs t) > > (One thing that's missing from this code is a check to verify that no > single element in the list is greater than the threshold, which should > raise an error, rather than get stuck in an infinite loop.) > > The algorithm as implemented works fine, but it seems overly > complicated > and not very elegant. I get the feeling that I'm missing some obvious > simplification, but I can't find it. Any ideas? > > Thanks, > > -Steve Schafer > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0