Also, if I understand correctly, solutions 1 & 2 will only produce one pair, whereas solution 3 (based on list comprehensions) will produce all pairs that sum to the total. On 27 July 2011 07:33, Gary Klindt wrote:

Hey all!

I compared the different methods proposed with my eyes and the profiler.

sumCheck1 _     []     _  = Nothing sumCheck1 total (x:xs) ys = if total' == Nothing                           then sumCheck total xs ys                           else return (x,(ys!!(fromJust total')))                           where total' = elemIndex (total-x) ys

sumCheck2 total (x:xs) ys =    let diff = total - x    in if elem diff ys       then Just (x,diff)       else sumCheck total xs ys

sumCheck3 i as bs = not $ null [(x,y) | x <- as, y <- bs, x+y==i ]

It is fascinating how small the code can be with list comprehensions. Unfortunately the third solution needs much more memory during run time than the other two. Increasing the list size leads to heavy growth of memory allocation. Probably the evaluation of the cross product in sumCheck3 is not very lazy (but why not?). The first two solutions scale very well.

Cheers

On 07/26/2011 08:31 AM, aditya siram wrote:

...

List comprehension seems like the easiest way to do it.

First here's how to get the cross product of two lists, I'll be using this below: cp as bs = [(x,y) | x<- as, y<- bs ] -- cp [1,2,3] [4,5,6] = [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Then constrain the cross product to tuples where the sum is the given number: sums i as bs = [(x,y) | x<- as, y<- bs, x + y == i] -- sums 4 [1,2,3] [1,2,3] == [(1,3),(2,2),(3,1)]

Then check that the list of constrained sums is not empty: sumCheck i as bs = not (null (sums i as bs))

-deech

On Mon, Jul 25, 2011 at 10:52 PM, Bryce Verdier  wrote:

...

Hi all, I'm new to haskell, and I'm trying to get better with it. Recently I completed one of the challenges from Programming Praxis and I was wondering if people would be willing to spend some time and tell me how I could improve my code. Thanks in advance, Bryce Here is a link to the programming praxis: http://programmingpraxis.com/2011/07/19/sum-of-two-integers/ And here is my code: import Data.List import Data.Maybe sumCheck :: Int ->  [Int] ->  [Int] ->  Maybe (Int, Int) sumCheck _ [] _ = Nothing sumCheck total (x:xs) ys = if total' == Nothing                                 then sumCheck total xs ys                                 else return (x, (ys !! ( fromJust total')))                            where total' = (total - x) `elemIndex` ys

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Hi! On Wed, Jul 27, 2011 at 09:47:14AM +1000, Jeff Lasslett wrote:

Also, if I understand correctly, solutions 1 & 2 will only produce one pair, whereas solution 3 (based on list comprehensions) will produce all pairs that sum to the total.

On 27 July 2011 07:33, Gary Klindt wrote:

...

sumCheck3 i as bs = not $ null [(x,y) | x <- as, y <- bs, x+y==i ]

Maybe I misunderstood you, but you aren't quite right. In third solution, *list comprehension* will produce all the pairs. But you're applying 'null' to it, and since everything in Haskell is lazy by default, only *one* pair will be produced. Just for your information: that's why it's always advised to use 'null' to check if list is empty. Newbies often try to do that in more obvious way: length list == 0 but that have very nasty consequence: to calculate length of the list, you should compute the value of each element. If you use null, only first (if any) element gets computed, and then null immediately returns. Ah, yes, one more note: first two solutions return pair that satisfies your task, while third solution will only return some Bool value indicating if such pair exists. -- Regards, Alexander Batischev 1024D/69093C81 F870 A381 B5F5 D2A1 1B35 4D63 A1A7 1C77 6909 3C81

Hi! On Wed, Jul 27, 2011 at 11:19:03AM +1000, Arlen Cuss wrote:

(Of course, this is less beautifully illustrated with 'length', because it doesn't actually evaluate the values ...:

...

length [trace "a" 5, trace "b" 10, trace "c" 15] == 0 False

Oh, excuse me - yes, 'length' really doesn't evaluate the values. But still, it *builds* the list (that may be very large or even infinite), thus slowing or even hanging your program. -- Regards, Alexander Batischev 1024D/69093C81 F870 A381 B5F5 D2A1 1B35 4D63 A1A7 1C77 6909 3C81

I repeated the profiling: print $ sumCheck 500 [1..1000] [1..1000] sumCheck1: 58,648 sumCheck2: 58,484 sumCheck3: 70,016 print $ sumCheck 5000 [1..10000] [1..10000] sumCheck1: 238,668 sumCheck2: 238,504 sumCheck3: 358,016 (unit: byte) This time I used the same compiler flags as Aditya (all but -rtsopts, I got:ghc: unrecognised flags: -rtsopts ). I'm using GHC version 6.12.1. Ok, in this numerical example, the scaling of sumCheck3 is not worse than the other's. In my first run I used quasi random numbers (fingers on my keyboard). Maybe you got puzzled with your '.prof' files? They seem identical (there always exists a function sum) On 07/27/2011 07:34 AM, aditya siram wrote:

I just profiled all three and have not found them to be different. Maybe I'm reading my profiler output wrong so I've pasted it below. The compilation command I used was: ghc -fforce-recomp -XBangPatterns -prof -rtsopts -auto-all -o ListCrossProductSum ListCrossProductSum.hs

They were all invoked using: main = print $ sumCheck 5000 [1..10000] [1..10000]

I am running GHC 7.0.1

-deech

sumcheck1: ========== Wed Jul 27 00:26 2011 Time and Allocation Profiling Report (Final)

ListCrossProductSum +RTS -p -RTS

total time = 0.00 secs (0 ticks @ 20 ms) total alloc = 344,084 bytes (excludes profiling overheads)

COST CENTRE MODULE %time %alloc

sums Main 0.0 40.7 main Main 0.0 58.3

individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc

MAIN MAIN 1 0 0.0 0.0 0.0 100.0 CAF Main 240 2 0.0 0.2 0.0 99.2 main Main 246 1 0.0 58.3 0.0 99.0 sumCheck Main 247 1 0.0 0.0 0.0 40.7 sums Main 248 1 0.0 40.7 0.0 40.7 CAF GHC.Show 236 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.FD 176 2 0.0 0.4 0.0 0.4 CAF System.Posix.Internals 175 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.Internals 140 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding.Iconv 134 2 0.0 0.3 0.0 0.3 CAF GHC.Conc.Signal 131 1 0.0 0.1 0.0 0.1

sumcheck2 ========= [1 of 1] Compiling Main ( ListCrossProductSum.hs, ListCrossProductSum.o ) True Wed Jul 27 00:27 2011 Time and Allocation Profiling Report (Final)

ListCrossProductSum +RTS -p -RTS

total time = 0.00 secs (0 ticks @ 20 ms) total alloc = 344,084 bytes (excludes profiling overheads)

COST CENTRE MODULE %time %alloc

sums Main 0.0 40.7 main Main 0.0 58.3

individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc

MAIN MAIN 1 0 0.0 0.0 0.0 100.0 CAF Main 240 2 0.0 0.2 0.0 99.2 main Main 246 1 0.0 58.3 0.0 99.0 sumCheck Main 247 1 0.0 0.0 0.0 40.7 sums Main 248 1 0.0 40.7 0.0 40.7 CAF GHC.Show 236 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.FD 176 2 0.0 0.4 0.0 0.4 CAF System.Posix.Internals 175 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.Internals 140 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding.Iconv 134 2 0.0 0.3 0.0 0.3 CAF GHC.Conc.Signal 131 1 0.0 0.1 0.0 0.1

sumcheck3 ========= ListCrossProductSum +RTS -p -RTS

total time = 0.00 secs (0 ticks @ 20 ms) total alloc = 344,084 bytes (excludes profiling overheads)

COST CENTRE MODULE %time %alloc

sums Main 0.0 40.7 main Main 0.0 58.3

individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc

MAIN MAIN 1 0 0.0 0.0 0.0 100.0 CAF Main 240 2 0.0 0.2 0.0 99.2 main Main 246 1 0.0 58.3 0.0 99.0 sumCheck Main 247 1 0.0 0.0 0.0 40.7 sums Main 248 1 0.0 40.7 0.0 40.7 CAF GHC.Show 236 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.FD 176 2 0.0 0.4 0.0 0.4 CAF System.Posix.Internals 175 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.Internals 140 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding.Iconv 134 2 0.0 0.3 0.0 0.3 CAF GHC.Conc.Signal 131 1 0.0 0.1 0.0 0.1