Finding the shortest list in a list of lists in Haskell

Question

I am having some difficulty with a program I've written using Haskell. The idea behind it is to recursively find the shortest list in a list of lists and return that. I've managed to write the program okay but I can't seem to figure out what I've done wrong in it. These are the errors that I get when I try to compile it:

Couldn't match type ‘a’ with ‘[[a]]’, ‘a’ is a rigid type variable bound by the type signature for: shortest :: forall a. [[a]] -> [a] at shortest.hs:1:13. Expected type: [[[a]]], Actual type: [a]
In the first argument of ‘shortest’, namely ‘y’. In the first argument of ‘(:)’, namely ‘shortest y’. In the expression: shortest y : [list]
Relevant bindings include list :: [[a]] (bound at shortest.hs:4:15), y :: [a] (bound at shortest.hs:4:13), x :: [a] (bound at shortest.hs:4:11), shortest :: [[a]] -> [a] (bound at shortest.hs:2:1).

Here is the code I'm using:

shortest :: [[a]] -> [a]
shortest [] = []
shortest [y] = y
shortest (x:y:list)
   | length x > length y = shortest y:[list]
   | otherwise = shortest x:[list]

If anyone could give me any pointers as to where I'm going wrong it would be much appreciated!

I think you just need parentheses. shortest (y:[list]) and the same for the x case. The precedence of : makes it read like (shortest y) : [list] — jkeuhlen
@jkeuhlen thank you! I literally just spotted that myself, been looking at it so long I wasn't seeing the obvious! — Chilly
glad that helped. I added it as an answer since that's the more permanent place for these kinds of things rather than comments. — jkeuhlen

chepner chepner · Accepted Answer · 2018-10-30T16:06:04

list is already the tail of your input; you don't need to (nor should you) wrap it in another list.

shortest (x:y:list) = shortest $ (if length x > length y then y else x) : list

At each step, it's just a question of which element, x or y, you remove from the input to the recursive call.

Another way, which doesn't require two base cases, is to just compare the head of the list to the result of recursing on the tail.

shortest [] = []
shortest (x:xs) = let s = shortest xs
                  in if length s < length x then s else x

Finally, tuples compare lexicographically, so you can also dispense with explicit recursion by tagging each list with its length, finding the smallest tagged value, then extracting the original list.

shortest = snd . minimum . map (\x -> (length x, x))

Using Control.Arrow, you can write the argument to map as (length &&& id).

Caveat for the last approach: since lists also compare lexicographically, the final result if you have multiple lists with the shortest length will depend on how the list values themselves compare. The first two examples, by contrast, are stable; the first such shortest list is returned.

Daniel Wagner points out a better solution for using minimum, which is to wrap each element in an Arg value which lets two lists be compared solely on their lengths, without considering the lists' contents.

import Data.Semigroup
shortest xs = x where Arg _ x = minimum [Arg (length x) x | x <- xs]

Arg is basically a 2-element product type which only uses the first element for its Ord instance, unlike (,) which uses both.

Finding the shortest list in a list of lists in Haskell

4 Answers