Haskell code optimisation

newer
Understanding Haskell Map.lookup...

older
Trouble understanding the type of...

Abhishek Kumar

11 Dec 2015 11 Dec '15

9:47 a.m.

I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation. ------haskell code f m n | m==0 =n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1)) Thanks Abhishek Kumar

Attachments:

attachment.html (text/html — 476 bytes)

Show replies by date

Sumit Sahrawat, Maths & Computing, IIT (BHU)

11 Dec 11 Dec

10:17 a.m.

Graham Hutton's paper "A tutorial on the expressiveness and universality of folds", provides a good introduction to folds, and implements the Ackerman function as an example. Folds were the first stumbling point for me when learning Haskell, and this paper helped me a lot. On 11 December 2015 at 20:17, Abhishek Kumar wrote:

...

I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code f m n | m==0 =n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1))

Thanks Abhishek Kumar

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-- Sumit Sahrawat, Junior - Mathematics and Computing, Indian Institute of Technology - BHU, Varanasi, India

Magnus Therning

13 Dec 13 Dec

4:58 p.m.

Sumit Sahrawat, Maths & Computing, IIT (BHU) writes:

...

Graham Hutton's paper "A tutorial on the expressiveness and universality of folds", provides a good introduction to folds, and implements the Ackerman function as an example. Folds were the first stumbling point for me when learning Haskell, and this paper helped me a lot.

To save others from a search: http://www.cs.nott.ac.uk/~pszgmh/fold.pdf /M -- Magnus Therning OpenPGP: 0x927912051716CE39 email: magnus@therning.org jabber: magnus@therning.org twitter: magthe http://therning.org/magnus Failure is not an option. It comes bundled with the software.

Kim-Ee Yeoh

11 Dec 11 Dec

10:44 a.m.

Have you tried BangPatterns? Compiled with optimization, I get 22 secs. Here's the full program: {-# LANGUAGE BangPatterns #-} f :: Int -> Int -> Int f !m !n | m==0 = n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1)) main = putStrLn (show (f 4 1)) -- Kim-Ee On Fri, Dec 11, 2015 at 9:47 PM, Abhishek Kumar wrote:

...

I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code f m n | m==0 =n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1))

Thanks Abhishek Kumar

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Abhishek Kumar

12 Dec 12 Dec

4:19 a.m.

Thanks Kim for your answer but as far as I understand strict evaluation should save in space as expression is not expanded in terms of thunks,but I can't understand time savings.Can you pls explain strict evaluation? On Friday, December 11, 2015, Kim-Ee wrote:

...

Have you tried BangPatterns? Compiled with optimization, I get 22 secs. Here's the full program:

{-# LANGUAGE BangPatterns #-}

f :: Int -> Int -> Int f !m !n | m==0 = n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1))

main = putStrLn (show (f 4 1))

-- Kim-Ee

On Fri, Dec 11, 2015 at 9:47 PM, Abhishek Kumar javascript:_e(%7B%7D,'cvml','abhishekkmr18@gmail.com');> wrote:

...
I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code f m n | m==0 =n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1))

Thanks Abhishek Kumar

_______________________________________________ Beginners mailing list Beginners@haskell.org javascript:_e(%7B%7D,'cvml','Beginners@haskell.org'); http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Kim-Ee Yeoh

6:41 a.m.

On Sat, Dec 12, 2015 at 4:19 PM, Abhishek Kumar wrote:

...

Thanks Kim for your answer but as far as I understand strict evaluation should save in space as expression is not expanded in terms of thunks,but I can't understand time savings.Can you pls explain strict evaluation?

For this particular problem, start here: https://en.wikipedia.org/wiki/Memory_hierarchy What happens to original program that has a sprawling mass of thunks all over RAM? The CPU spends most of its time waiting on the memory bus. And that's not even going into things like disk-backed virtual mem. -- Kim-Ee

Abhishek Kumar

7:35 a.m.

Compiling below code (ghc --make) still doesn't gives result on my i3 Ubuntu 64bit machine.Can u please elaborate optimisations you did? Thanks Abhishek On Friday, December 11, 2015, Kim-Ee Yeoh wrote:

...

Have you tried BangPatterns? Compiled with optimization, I get 22 secs. Here's the full program:

{-# LANGUAGE BangPatterns #-}

f :: Int -> Int -> Int f !m !n | m==0 = n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1))

main = putStrLn (show (f 4 1))

-- Kim-Ee

On Fri, Dec 11, 2015 at 9:47 PM, Abhishek Kumar javascript:_e(%7B%7D,'cvml','abhishekkmr18@gmail.com');> wrote:

...
I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code f m n | m==0 =n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1))

Thanks Abhishek Kumar

_______________________________________________ Beginners mailing list Beginners@haskell.org javascript:_e(%7B%7D,'cvml','Beginners@haskell.org'); http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Dimitri DeFigueiredo

7:57 a.m.

with 'ghc -O2' this takes 14 seconds on my macbook pro. Dimitri On 12/12/15 10:35 AM, Abhishek Kumar wrote:

...

Compiling below code (ghc --make) still doesn't gives result on my i3 Ubuntu 64bit machine.Can u please elaborate optimisations you did? Thanks Abhishek

On Friday, December 11, 2015, Kim-Ee Yeoh mailto:ky3@atamo.com> wrote:

Have you tried BangPatterns? Compiled with optimization, I get 22 secs. Here's the full program:

{-# LANGUAGE BangPatterns #-}

f :: Int -> Int -> Int f !m !n | m==0 = n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1))

main = putStrLn (show (f 4 1))

-- Kim-Ee

On Fri, Dec 11, 2015 at 9:47 PM, Abhishek Kumar javascript:_e(%7B%7D,'cvml','abhishekkmr18@gmail.com');> wrote:

I was trying to write below program for ackerman function but it fails (waits too long) for ack(4,1) whereas a recursive C program gives result in 37secs.Can someone pls explain this behaviour and recomend some optimisation.

------haskell code f m n | m==0 =n+1 | n==0 = f (m-1) 1 | otherwise = f (m-1) (f m (n-1))

Thanks Abhishek Kumar

_______________________________________________ Beginners mailing list Beginners@haskell.org javascript:_e(%7B%7D,'cvml','Beginners@haskell.org'); http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

3446

Age (days ago)

3448

Last active (days ago)

List overview

Download

7 comments

5 participants

participants (5)

Abhishek Kumar
Dimitri DeFigueiredo
Kim-Ee Yeoh
Magnus Therning
Sumit Sahrawat, Maths & Computing, IIT (BHU)