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?

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
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 '14 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 '14 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 '14 at 4:34
  • @Carcigenicate Yep :) – Daniel Gratzer Jul 22 '14 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.

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 '15 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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