up vote 4 down vote favorite

I don't understand why I can't construct a list that looks like [1,"1",1.1] in haskell. I don't think it's static typing that gets in the way because I thought that head would now have an ill defined type but then I thought about it and there is no reason the run-time system doesn't instantiate a different version of head whenever a list is fed into it so head [1,"1",1.1] would be typed as List->Int and head (tail [1,"1",1.1]) would be typed as List->String. Since the run-time already does a lot of bookkeeping why doesn't it provide fancier polymorphic (or is it generic) versions of the various prelude functions? What am I missing here?

share|improve this question
3  
@davidk01: tell me the type of the 4th element of a list variable... in other words a list which is an argument to a function? For that matter, tell me whether it even has a 4th element, at compile time! If either the list or the index is a variable, you can't know the type at compile time. – Tom Crockett Jan 5 '11 at 7:22
2  
davidk01: That's the problem -- the compiler doesn't know the specific number. If the compiler encounters [1,"1",1.1] !! n it can't tell what the type of the expression will be. – Gabe Jan 5 '11 at 7:23
5  
davidk01: The fact that you can't tell me its type is the reason you can't construct such a list -- you answered your own question. If you know your list will always be an Int, a String, and a Float you have a tuple rather than a list. – Gabe Jan 5 '11 at 7:29
2  
@davidk01: read carefully what @Antal S-Z said... exceptions are not returned values. – Tom Crockett Jan 5 '11 at 7:48
2  
@davidk01: You're not "too stupid to realize what's good for you", and I'm pretty sure that whatever you're trying to do is perfectly reasonable. However, I suspect you are misunderstanding some terminology--such as the true meaning of "static typing" and what that entails for run-time vs. compile-time knowledge--resulting in an awkward communication barrier. Types in Haskell are not simply like types in Javascript or Ruby except known ahead of time; the difference is deeper. I might be able to clarify things, but it would be lengthy and not really answer this question itself... – C. A. McCann Jan 5 '11 at 22:11
up vote 16 down vote accepted

It is indeed the typing that prevents this. Consider the definition of a list (notice the type parameter a, which is missing from your types):

data List a = Nil | Cons a (List a)

In the Cons a (List a) you can see that the type of thing at the head of the list must be the same type as the elements that follow it. To answer your question, you're not missing a lot: as you say the runtime could do it, but in Haskell you want to make these typing decisions at compile-time, not runtime.

If you want heterogeneous lists, you can see some wizardry by Oleg Kiselyov in his work on HList (= Heterogeneous List). It may not be exactly what you want, but it's in the same rough direction.

share|improve this answer
1  
+1 for HList!!! – Landei Jan 5 '11 at 7:35
5  
And for the sake of clarity, HList's "heterogeneous lists" are really no different from right-nested 2-tuples. The interesting part isn't the lists themselves, it's the crazy type-level meta-programming deep magic Oleg uses to construct generic functions that work on arbitrary "lists". – C. A. McCann Jan 5 '11 at 17:37
2  
@davidk01: the above is what you actually need to know. At this point in your learning you don't need to know about HList or other type-hackery. Learn the basics first. – Paul Johnson Jan 6 '11 at 21:25
up vote 3 down vote

Because in Haskell all types are known at compile-time. There's no such thing as waiting until runtime to see what the type will be. And because this is sufficient to do anything you could want to do in a dynamically-typed system, while being easier to reason about to boot.

share|improve this answer
1  
@davidk01: it will be known at runtime, yes, but not at compile-time. It's easy to see what the type of the 2nd element of [1, "1.1", 1.1] is, because you're looking at a list literal, but what if you're trying to determine the nth element of an arbitrary list that is an argument to a function? – Tom Crockett Jan 5 '11 at 7:19
2  
@davidk01: And what would the type of [1, "1.1", 1.1] be? You can't give it a sensible type other than something like HCons Integer (HCons String (HCons Double HNil)). This works (the HList module supports such lists, and gives them types like that), but you can see why it's not the default. Such lists are far less flexible than your standard [a], and (IMHO) you'll usually want a tuple instead. – Antal Spector-Zabusky Jan 5 '11 at 7:37
1  
@davidk01: as @Gabe pointed out, you want a tuple, not a list... if a heterogeneous list can be of variable length then it is impossible to know the types of each of the elements at compile-time because you don't even know how many elements it has at compile-time. – Tom Crockett Jan 5 '11 at 7:41
4  
@davidk01: Here's a heterogeneous list with known length, you can use fst and snd instead of head and tail on it: (1, ("1.1", (1.1, 'c'))) – Tom Crockett Jan 5 '11 at 8:02
1  
@davidk01: I think it's actually possible to have heterogenous lists in a static programming language, but you may need dependent types. – fuz Jan 5 '11 at 11:48
up vote 3 down vote

Just so you know, there actually is a package for heterogeneous lists, using non-trivial techniques and you really should make sure you understand the type system well before diving into this. You don't have this by default because of the type system. A list in Haskell isn't just a list. It's a list of a's, 'a' being Int, String, whatever you want. BUT, one list can contain only one type of values.

Note that you can define "heterogeneous lists" of elements satisfying some constraints using existential quantification, but I think you're not there yet and really should focus on understanding the other answers here before going any further.

share|improve this answer
    
+1 for the important point that Haskell lists are meant to be a list of a's. – John L Jan 5 '11 at 15:48
up vote 3 down vote

There is a heteregenous list type called HList (available on Hackage), but note that there probably is a type for the contents of your list. Consider something like this:

history = [-12, "STATEMENT END", (-244, time January 4 2010), ...]

Your data has a type struggling to emerge, e.g.:

data HistoryEntry = Withdrawal Int | StatementClosing | ScheduledPayment Int CalendarTime

history = [Withdrawal 12, StatementClosing, ScheduledPayment 244 (time January 4 2010)]

In many cases, your data has a type that you just need to seek out.

share|improve this answer
up vote 3 down vote

Look at Heterogenous collections

{-# OPTIONS -fglasgow-exts #-}
--
-- An existential type encapsulating types that can be Shown
-- The interface to the type is held in the show method dictionary
--
-- Create your own typeclass for packing up other interfaces
--
data Showable = forall a . Show a => MkShowable a

--
-- And a nice existential builder
--
pack :: Show a => a -> Showable
pack = MkShowable

--
-- A heteoregenous list of Showable values
--
hlist :: [Showable]
hlist = [ pack 3
        , pack 'x'
        , pack pi
        , pack "string"
        , pack (Just ()) ]

--
-- The only thing we can do to Showable values is show them
--
main :: IO ()
main = print $ map f hlist
    where
        f (MkShowable a) = show a

{-

*Main> main
["3","'x'","3.141592653589793","\"string\"","Just ()"]

-}
share|improve this answer
    
This isn't HList, it's existential types. – AndrewC Sep 21 '12 at 16:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.