Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 5 down vote favorite

I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type 'a -> 'b. Now I've been experimenting a bit with functions of type 'a list -> 'b list. There are some obvious simple examples:

let rec loop l = loop l
let return_empty l = []
let rec loop_if_not_empty = function [] -> []
                                   | l -> loop_if_not_empty l

What I can't figure out is how to make a function that does something other than return the empty list or loop (without using any library function). Can this be done? Is there a way to return non-empty lists?

Edit: Yes, if I have a function of type 'a -> 'b, then I can make another one, or a function of type 'a list -> 'b list, but what I'm wondering here is how to make the first one.

share|improve this question
1  
As with the previous question, please target the CS101 student learning programming in your answer, not the type theoretist that your answer might inspire him to later become. – Gilles♦ Mar 14 '12 at 0:12
Notice that if you had a function f with this type returning a non empty list then fun a -> List.hd (f [ a ]) would have type 'a -> 'b without being non-terminating or raising an exception. – gallais Mar 14 '12 at 0:49

1 Answer

up vote 4 down vote

Let's get back to simpler objects: you cannot build an proper object of type 'a because then it would mean this object x can be used wherever 'a would fit. And that means everywhere: as an integer, an array, even a function. For example that would mean you can do things like x+2, x.(1) and (x 5). Types exist exactly to prevent this.

This the same idea that apply with a function of type 'a -> 'b, but there are some cases where this type can exists: when the function never returns an object of type 'b: when looping or raising an exception.

This also apply to functions that return a list. If your function is of type t -> 'b list and that you build an object of type t and apply it to this function, then that means that if you successfully access an element of this list then you will access to an object that have all types. So you can't access any element of the list: the list is either empty or ... there is no list.

However the type 'a list -> 'b list appears in usual exercises but that's only when you already have a function of type 'a -> 'b:

let rec map (f : 'a -> 'b) =
  function
  | [] -> []
  | x :: xs -> f x :: map f xs

But you probably know this one.

val map : ('a -> 'b) -> 'a list -> 'b list
share|improve this answer
1  
Is the type of map not usually 'a list -> ('a -> 'b) -> 'b list? It seems a more natural order w.r.t. currying. – Raphael♦ Mar 14 '12 at 7:07
1  
Well it is quite standard in OCaml, Haskell, Caml Light, SML, Lisp or even theoretical monads. It seems natural to me: you can define a function like let double_list = List.map (( * ) 2). Do you have an example where currying with the list first is interesting? – jmad Mar 14 '12 at 10:07
1  
('a -> 'b) -> 'a list -> 'b list reflects the fact that map is just the lifting of functions wrt the functor list. – gallais Mar 14 '12 at 10:12
Never mind; I should not write comments before breakfast. Thanks for your explanations. – Raphael♦ Mar 14 '12 at 10:20
The older type theorist is less than thrilled by this answer. Ok, a non-empty type variable context is a way to have a function that's literally of type 'a -> 'b or 'a list -> 'b list, but that's not such an interesting observation. In fact I'm going to edit the question to make it clear this isn't what the younger student learning programming was wondering about. – Gilles♦ Mar 15 '12 at 1:00
show 1 more comment

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.