Check for a list in Haskell

Question

The Little Schemer has a function to check if the list is flat:

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

I am trying to write the same recursive function in Haskell, but have not succeeded:

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

How to 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]]] are not.

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

EDIT: I see that people get confused because of a signature like is_lat :: [a] -> Bool . I agree with this that I should not check type at runtime. However, is it possible to check the type at compile time? How can I make a function work only for flat lists? Or should I completely change my mindset?

Answer 1

You cannot think of nested lists in the same way in Haskell as in Scheme, because this is not the same data structure. Haskell's list is homogeneous, where as a Lisp, the "list" is actually closer to the rosewood (as indicated in CAMcCann below). As an illustrative example, consider how the parsing section WYAS48 defines LispVal .

If you really, really, really want to do runtime type checking, although this is usually a bad idea and very unconventional in Haskell, see Data.Typeable . This answer may also be helpful.

The real answer to this question is: “You need to think differently about your arguments in Haskell than in Lisp, which means you never need to run this check yourself at runtime” (and I say this as Common Lisper, therefore I understand how to upset this to start with).

Addition . In response to your editing, a system like Haskell automatically provides this. For example, if you have a function like foo :: [Int] -> Int and you pass it ["One", "Two", "Three"] or [[1, 2, 3]] , you will get a time error a compilation telling you what just exploded and why. If you want to specialize a function, just declare a more specific type.

For example (do not write such code, this is just for illustrative purposes), let's say you have a simple function, like

 myLookup index map = lookup index map 

If you load this into GHCi and run :t myLookup , it will tell you that the function type is myLookup :: Eq a => a -> [(a, b)] -> Maybe b means that it can take a key of any type, which outputs Eq (all you can run == on). Now say that for some reason you want you to only use numbers as keys. You need to make sure that adding a more specific declaration like

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

Now, although there is nothing in the function body that would prevent it from dealing with other types of keys, you will get a type error at compile time if you try to pass it something other than the Int index or something other than the map [(Int, a)] . As a result

 myLookup :: Int -> [(Int, a)] -> Maybe a myLookup ix lst = lookup ix lst main :: IO () main = putStrLn . show $ myLookup 1 [(1, "Foo")] 

will compile and work fine, but it

 myLookup :: Int -> [(Int, a)] -> Maybe a myLookup ix lst = lookup ix lst main :: IO () main = putStrLn . show $ myLookup "Nope.jpg" [("Foo", 1)] 

will not. On my machine, these are errors during compilation 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 this didn’t bother you anymore.

Answer 2

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

eg. if you try to create a mixed list, you will get an error message 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!"]] 

Answer 3

The function type [a] -> Bool implicitly means forall a. [a] -> Bool forall a. [a] -> Bool , in other words, it is defined identically for lists of all possible types of elements. This includes types like [[Int]] or [[[String]]] or any nesting depth you can think of. But this is not so - and it does not matter for your function what the type of the element is.

As for this function, an input is always a list whose elements are an opaque unknown type. It will never receive nested lists containing the same opaque type.

Answer 4

Well, I think 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-strongly typed languages, every object has runtime type information and, therefore, can be polymorphic. It can be a complicated coercive network, for example, in Scala (less complicated if you are in C ++), or simply “everything is an object, and an object is everything”, as in purely dynamic languages ​​(Lisp, JS, ... )
Haskell is strongly typed.