1

I have the following small function that uses foldr to find the largest second number of a 2-tuple:

listMax :: [(Int,Int)] -> Int
listMax = snd . foldr (\(_,freq1) (_,freq2) -> (0,max freq1 freq2)) (0,0)

My question pertains to the body of the lambda:

(0,max freq1 freq2)

I had to make it into a tuple with a dummy head so that it matches it's own input for the fold. To me though, it looks ugly and makes it harder to read. Is this the standard way of dealing with this situation, or is there a idiomatic way around this?

Improve this question

2 Answers 2

Reset to default
4

Well I'd probably write it as

listMax :: [(Int,Int)] -> Int
listMax = foldr max 0 . map snd

List fusion should actually make this compile to the same thing in the end :)

Worth noting that this is technically incorrect as it will misbehave with all negative numbers.

listMax = foldr max minBound . map snd
Improve this answer
4
  • Love it; that's much neater. Won't this run exponentially slower though, as it will have to traverse the list twice (Once during the mapping, then again during the fold)? And what about it doesn't like negative numbers? Max is compatible with them isn't it? (Untested, but they should be members of Ord like positive numbers). Thank you
    – Carcigenicate
    Jul 22, 2014 at 4:16
  • 1
    @Carcigenicate 1. Listfusion means we can optimize this into one pass, even if we don't it doesn't impact algorithmic complexity 2. The problem with negatives is that 0 is greater than them! So you'll just end up with 0 in the end
    – daniel gratzer
    Jul 22, 2014 at 4:30
  • 1. Cool. Never heard of list fusion. I'll look into it. 2. Dur -_-. I must be tired. Let me guess, minBound is the lowest number possible, so anything compared against it will be higher ensuring it doesn't get stuck?
    – Carcigenicate
    Jul 22, 2014 at 4:34
  • @Carcigenicate Yep :)
    – daniel gratzer
    Jul 22, 2014 at 4:35
0

As jozefg pointed out, your version is incorrect for negative numbers, as it gives 0.

I would write 

listMax = foldr1 max . map snd

The difference between my solution and theirs is the behavior for empty lists. Mine gives an exception, which I think is appropriate, since an empty list has no minimum. Theirs returns minBound.

Improve this answer
1
  • 1
    I'd suggest using Maybe rather than an exception here. The type [(Int, Int)] -> Int says to me that this function accepts all lists including empty onces. Rather than rely on documentation we can force the user to be aware of the limitations of this function by saying [(Int, Int)] -> Maybe Int. Force the failure to be explicit especially given the awkwardness of exceptions in Haskell.
    – daniel gratzer
    Jan 5, 2015 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.