Recursive Function on a List in Haskell

Question

I want to get the max and min value out of a List as a tuple by using recursion. I tried it with this code below and cant really figure out why it does not work. I would really appreciate a small hint what my error in reasoning is. Thanks much

seekMaxMin :: [Double] -> (Double,Double)
seekMaxMin [] = (0,0)
seekMaxMin [x] = (x,x)
seekMaxMin (x:rest) = (max x(seekMaxMin rest), min x(seekMaxMin rest))

"cant really figure out why it does not work." But you got a type error, didn't you? — user824425
– user824425, Commented Apr 30, 2014 at 11:34

monocell · Accepted Answer · 2014-04-30 16:54:35Z

5

seekMaxMin returns a tuple of both the min and the max, but in your last equation you pretend first that it only returns the max and secondly that it only returns the min. You can use a pattern to extract them both and get rid of the redundant walk down the list as well.

seekMaxMin (x:rest) = (max x rmax, min x rmin)
    where (rmax, rmin) = seekMaxMin(rest)

I'm also a little bit opposed to making the min of an empty list of doubles be 0, but perhaps it's suitable for whatever purpose you have with this function.

edited Apr 30, 2014 at 16:54

answered Apr 30, 2014 at 11:17

monocell

1,44111 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user3588998 Over a year ago

thanks a lot, i did not know this syntax is possible. But im really a newbie in programming..

ars-longa-vita-brevis · Accepted Answer · 2014-04-30 12:14:24Z

0

Monocell's answer is the one I'd recommend. However, looking at your code, I think the logic you might have been thinking of is:

seekMaxMin :: [Double] -> (Double,Double)
seekMaxMin [] = (0,0)
seekMaxMin [x] = (x,x)
seekMaxMin (x:rest) = (maximum $ x:[fst $ seekMaxMin rest], minimum $ x:[snd $ seekMaxMin rest])

answered Apr 30, 2014 at 12:14

ars-longa-vita-brevis

7351 gold badge8 silver badges18 bronze badges

3 Comments

Simon Bergot Over a year ago

why are you using 2 recursive calls?

ars-longa-vita-brevis Over a year ago

@Simon, good point, they could probably be refactored into a where. I'm not sure if that's premature optimization though (?)

Simon Bergot Over a year ago

In this case no. The point of seekmaxmin is to compute max & min in one traversal. With your version, you get 2^n complexity which is hudge. Simply using built in maximum & minimum functions would still yield linear complexity.

Collectives™ on Stack Overflow

Recursive Function on a List in Haskell

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related