CODEWITHSUNDEEP
haskell
BullyWiiPlaza
BullyWiiPlaza

Reputation: 19195

All Same Lengths Function

I'm trying to write a function [a] -> Bool which returns true when all elements of the list have the same lengths.

I tried to do this using list recursion and extracted the first two elements of the list with x : y : xs then compared the length of x and y with length x == length y as case determination. However, GHCi complains about the types of x and y:

Couldn't match expected type `a' with actual type `[a0]'
  `a' is a rigid type variable bound by

      the type signature for [a] -> Bool
In the first argument of `length', namely `x'
In the first argument of `(==)', namely `length x'
In the expression: length x == length y

Why is this happening and how do I fix it? Clearly, length :: [a] -> Int == length :: [a] -> Int returns a Bool which is correct. In fact, replacing this expression by True compiles.

Upvotes: 1

Views: 886

Answers (3)

amalloy
amalloy

Reputation: 91897

The answers given so far don't work well when at least one list is list is finite and at least one is infinite: the function fails to terminate, when termination is possible, because they are busy calling length on an infinite list. Below is an answer that works for any sort of list:

allSameLength :: [[a]] -> Bool
allSameLength [] = True
allSameLength xs = all null xs || all (not . null) xs && allSameLength (map tail xs)

It's a pretty easy recursive definition: either all the lists are empty, or none of them are empty and they're still the same length after you take out one element from each.

Upvotes: 0

alternative
alternative

Reputation: 13012

We can do this very simply, actually.

 sameLengths :: [[a]] -> Bool
 sameLengths [] = True
 sameLengths (x:xs) = all (\y -> length y == length x) xs

No need for any recursion - all of the lengths are the same iff they are equal to the first one, so just extract the first and use all to easily check the rest.

As for why you can't define for [a], remember that [String] is a [[a]] as well as an [a]. But we specifically need [[a]] because length must be defined for whatever a is in [a].

Upvotes: 5

Alessio G. B.
Alessio G. B.

Reputation: 120

There are two problems:

  1. the length function is defined on lists (length :: [a] -> Int), so you can not apply it to other types

  2. you can certainly define a your own class:

    class WithLength a where
    myLength :: a -> Bool

    but you must define an instance of this class for each possible type! For example:

    instance WithLength Int where
    myLength _ = 1

instance WithLength [a] where
    myLength lst = length lst

    Then, you can define you recursive function to check the same length properies.

Upvotes: 0

Related Questions