2

The question is like this:

Write a function that takes an integer list and returns its length and the second largest integer in the list.

I can solve this with two functions but is there any solution that use only one function to do it?

Any help is appreciated! Thanks!

Zip
  • 809
  • 2
  • 14
  • 30
  • 1
    What's your definition of "1 function" vs "2 functions"? You can put the second one in a `where` clause of the first one, then it's only one function :) – us2012 Oct 01 '13 at 21:55
  • The general solution for finding the top k items (and therefore the kth largest item) in a single pass uses a priority queue, so you always know the top k so far at every step through the iteration. There's a blog post [here](http://stevehanov.ca/blog/index.php?id=122). For very small k, a priority queue might be overkill in performance terms, but it's probably easiest to stick with it - don't optimise prematurely IOW. I'm sure there's a suitable priority queue in the Haskell library somewhere. –  Oct 01 '13 at 22:14
  • 4
    @Steve314 I think that is unnecessary in Haskell, as the lazy evaluation means that using something like take k (sort xs) should be efficient. – Adam Gordon Bell Oct 02 '13 at 00:52
  • 3
    @Steve314 With GHC's implementation of `sort`, the `take k (sort xs)` trick is asymptotically optimal. – Daniel Wagner Oct 02 '13 at 01:03
  • 2
    @Steve314 This is a win of laziness over strictness, not functional over imperative. See also [my answer to this question](http://stackoverflow.com/questions/7868507/non-trivial-lazy-evaluation/7868790#7868790) which tries to explain the core advantage of laziness. – Daniel Wagner Oct 02 '13 at 01:05
  • @Daniel Wagner - I'm not scoring very well today, eh! OK, I see the point. –  Oct 02 '13 at 01:07
  • What should it return for a list of just one element? – Sassa NF Oct 02 '13 at 08:44

4 Answers4

4

Don't make it complicated.

f xs = (sort xs !! 1, length xs)

If you choose to make it complicated, make it complicated in the right way.

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • 1
    I interpreted 'second largest integer' to be in terms of magnitude. I.e. in `[1,1,2,3,3]`, we'd want 2. (psst, your sort order is backwards ;) ). – jtobin Oct 02 '13 at 01:38
  • As Daniel hasn't fixed this yet - to change the `sort` order, use [`sortBy`](http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-List.html#v:sortBy). Or, in the spirit of the existing code, use something like `reverse . sort $ xs !! 1`. Or, as `length xs` is being evaluated anyway, use `sort xs !! (length xs - 2)`. –  Oct 03 '13 at 00:24
3

Edited to use @ThomasM.DuBuisson's suggestion

You can solve this the same way that you could finding the max: using a fold. Max can be pretty trivially implemented with

mymaximum :: Ord a => [a] -> a
mymaximum xs = foldl searcher (head xs) xs
    where
        searcher :: Ord a => a -> a -> a
        searcher a b
            | a > b     = a
            | otherwise = b

So we can implement it similarly by just keeping up with the two largest values (notice that we have to "seed" the fold with a tuple as well):

nextmaximum :: Ord a => [a] -> a
nextmaximum xs = fst $ foldl searcher (h, h) xs
    where
        h = head xs
        searcher :: (Ord a) => (a, a) -> a -> (a, a)
        searcher (s, f) x = (min f (max s x), max f x)
Community
  • 1
  • 1
bheklilr
  • 53,530
  • 6
  • 107
  • 163
2

You can just compose individual functions together. This is neither efficient nor robust, but it's sure easy to write:

f xs = maximum . filter (< maximum xs) $ xs
jtobin
  • 3,253
  • 3
  • 18
  • 27
1
head . (!!1) . group . sortBy (flip compare) $ [1,1,2,3,4,4,4,5,5,6,6,6,6]
5
klapaucius
  • 1,094
  • 8
  • 6