Check if list is flat in Haskell

Question

In The Little Schemer there is a function to check, whether the list is flat:

(define lat?
  (lambda (l)
    (cond
     ((null? l) #t)
     ((atom? (car l)) (lat? (cdr l)))
     (else #f))))

I'm trying to write the same recursive function in Haskell, but have no success:

is_lat :: [a] -> Bool
is_lat [] = True
is_lat ???

How do i check that the parameter is not in the form [[a]]? In other words, [1,2,3] is a valid input, but [[1,3], [2,4]] and [[[1,2,3]]] aren't.

I want to use this further in recursive functions that accept lists to make sure that i deal with flat lists only.

EDIT: I see that people are confused because of the is_lat :: [a] -> Bool type signature. I agree now, that i shouldn't check type on runtime. However, is it possible to check the type on compile-time? How can i make the function work only for flat lists? Or should i completely change my way of thinking?

Unstrap

The question is: why do you want this? How do you plan to use this function? – Outdoors

Could you maybe just check for each element if it is a list? – Tegan

If [[[1, 2, 3]]] is not a valid input, your function has the wrong type and you might need to reconsider what you're trying to accomplish. – Dallon

What does it mean for a list to be flat? In Haskell, all lists must have elements of the same type. – Huntley

Why should it only work for flat lists? If you require something of the elements it may make sense to limit it to a fixed type like [Int] -> Bool or a type class Num a => [a] -> Bool, but if it should work for any element type, why can't the element type be a list? – Scatter

This should not be a solution used anywhere but, you could serialize your value with show : lat :: (Show a) => [a] -> Bool, lat = (/=)'['.flip(!!)1.show. – Caduceus

Answer 1

You can't really think of nested lists the same way in Haskell as in Scheme, because they're not the same data structure. A Haskell list is homogenous, where as a Lisp "list" is actually closer to a rose tree (as pointed out by C.A.McCann below). As an illustrative example, take a look at how the WYAS48 parsing section defines LispVal.

If you really, really, really want to do runtime type checking, even though it's usually a bad idea and very unconventional in Haskell, look into Data.Typeable. This response might be useful too.

The real answer to this question is "You need to think about your arguments differently in Haskell than in Lisp, which results in never needing to perform this check yourself at runtime" (and I say this as a Common Lisper, so I understand how frustrating that is to start with).

Addendum: In response to your edit, Haskell's type system automatically ensures this. If you have a function of type foo :: [Int] -> Int, for example, and you pass it ["One", "Two", "Three"] or [[1, 2, 3]], you'll get a compile-time error telling you what just exploded and why. If you want to specialize a function, just declare a more specific type.

For instance (don't write code like this, it's just for illustrative purposes), say you have a simple function like

myLookup index map = lookup index map 

If you load this into GHCi and run :t myLookup, it'll tell you that the functions' type is myLookup :: Eq a => a -> [(a, b)] -> Maybe b which means that it can take a key of any type that derives Eq (anything you can run == on). Now, say that for whatever reason you want to ensure that you only use numbers as keys. You'd ensure that by adding a more specific type declaration

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup index map = lookup index map 

Now, even though there's nothing in the body of the function preventing it from dealing with other key types, you'll get a type error at compile time if you try to pass it something other than an Int index or something other than an [(Int, a)] map. As a result, this

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup ix lst = lookup ix lst

main :: IO ()
main = putStrLn . show $ myLookup 1 [(1, "Foo")]

will compile and run fine, but this

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup ix lst = lookup ix lst

main :: IO ()
main = putStrLn . show $ myLookup "Nope.jpg" [("Foo", 1)]

will do neither. On my machine it errors at compile time with

/home/inaimathi/test.hs:5:35:
    Couldn't match expected type `Int' with actual type `[Char]'
    In the first argument of `myLookup', namely `"Nope.jpg"'
    In the second argument of `($)', namely
      `myLookup "Nope.jpg" [("Foo", 1)]'
    In the expression:
      putStrLn . show $ myLookup "Nope.jpg" [("Foo", 1)]
Failed, modules loaded: none.

I really hope that didn't confuse you further.

Calandracalandria

Note that most often, when you really, really, really want to do runtime type checking, you're mistaken and actually don't want to, because it's a bad approach. Even in languages with dynamic typing, explicit type checks are usually considered bad form. In particular, there is absolutely no situation where a beginner should be mucking around with Typeable. – Dallon

@C.A.McCann - Agreed. The snippet from the OP is a pretty common recursion situation in Lisps (and in Erlang, from what I've seen) where you want to check whether the next thing is an atom or another sequence and branch accordingly. You never need to do it unless you're dealing with heterogeneous lists. – Calandracalandria

It makes sense in that situation because cons cells are traditionally a sort of all-purpose data structure in lisps. In Haskell, you'd use a rose tree to express that kind of structure. – Dallon

Answer 2

This is both impossible and unnecessary with standard Haskell lists because Haskell is strongly typed; either all elements of a list are themselves lists (in which case the type is [a] = [[b]] for some b), or they are not.

E.g. if you try to construct a mixed list, you will get an error from the compiler:

Prelude> ["hello", ["world!"]]

<interactive>:3:12:
    Couldn't match expected type `Char' with actual type `[Char]'
    In the expression: "world!"
    In the expression: ["world!"]
    In the expression: ["hello", ["world!"]]

Bailment

it's not about mixed list, but about [a] and [[a]] – Unstrap

@sindikat: But those are different types. The first is a list whose elements are of type a. The second is a list whose elements are of type [a]. So a function for which answering your question makes sense would have to be one that takes a list where the elements are of different types (a and [a] to be specific). Such lists are heterogeneous, and Haskell lists are not. – Costate

Answer 3

The function type [a] -> Bool implicitly means forall a. [a] -> Bool, in other words it's defined identically for lists of all possible element types. That does include types like [[Int]] or [[[String]]] or any depth of nesting you can think of. But it doesn't--and can't--matter to your function what the element type is.

As far as this function is concerned, the input is always a list whose elements are some opaque, unknown type. It will never receive nested lists containing that same opaque type.

Dallon

Answer 4

Well, I guess, in Haskell you are limited to http://ideone.com/sPhRCP:

main = do   -- your code goes here
    print $isFlat [Node 1, Node 2, Node 3]
    print $isFlat [Node 1, Node 2, Branch [Node 3, Node 4, Node 5], Node 6]

data Tree a = Node a | Branch [Tree a]

isFlat :: [Tree a] -> Bool
isFlat = all isNode where
                      isNode (Node _) = True
                      isNode _ = False

In non strictly-typed languages every object has run-time type information and thus can be polymorphic. This might be a complicated network of coercions, like in Scala (less complicated if you're in C++), or just "everything is an object, and object is everything" like in purely dynamic languages (Lisp, JS, ...).
Haskell is strictly-typed.

Borzoi