1

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!

Improve this question
3
  • 1
    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] Commented Oct 30, 2018 at 15:58
  • @jkeuhlen thank you! I literally just spotted that myself, been looking at it so long I wasn't seeing the obvious! Commented Oct 30, 2018 at 15:59
  • glad that helped. I added it as an answer since that's the more permanent place for these kinds of things rather than comments. Commented Oct 30, 2018 at 16:02

4 Answers 4

Reset to default
4

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.

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

3 Comments

Your final solution has the downside that it requires an Ord a constraint, and with many lists of the same length may do much more work. Consider using Arg instead of a tuple to alleviate these two problems (note its instance Ord a => Ord (Arg a b) which does not require Ord b in its context).
Yes, that's a bigger issue than the one I pointed out. Is there a better way to unwrap the Arg value in the end? Also, is there a way to simplify that using ArgMin?
For a complete worked solution, consider shortest xs = x where Arg _ x = minimum [Arg (length x) x | x <- xs]. You can use ArgMin, but it's a bit noisier syntactically.
4 
 shortest []=[] shortest [y] = y shortest (x:y:list) |length x > length y = shortest (y:list) |otherwise = shortest (x:list)

This works :), also worth mentioning is if you have 2 or several elements in the list which are "shortest" the first element will always pop out.

i.e.

 Prelude>shortest[[1],[2],[3]] [1]
Improve this answer

Comments

3 
import Data.List import Data.Ord shortest list = minimumBy (comparing length) list

point-free:

shortest = minimumBy (comparing length)

These libraries are included with GHC. Their names say what they do pretty well. Perhaps add in a separate case for empty list.

Improve this answer

1 Comment

Or even minimumBy $ comparing length.
2

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

Improve this answer

2 Comments

right, although, (y:[list]) is also wrong. you need to correct that. ( (1:[2]) == [1,2] ).
@WillNess Thanks! Fixed now. I just threw this together as a quick comment and moved it to an answer when the OP said it worked for them. I probably should have done more due diligence in the comment->answer transition.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.