listhaskellrecursionpattern-matchingthe-little-schemer

Check if list is flat in Haskell


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?


Solution

  • 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.