On Mon, Jan 07, 2008 at 12:36:12AM -0800, SJS wrote:
It also requires type variables, since there might be parts of a type that
just aren't known. E.g. (in something resembling Haskell)
map f [] = []
map f (x:r) = (f x) : (map f r)
It allows patterns at the top level as basically a case statement. The
Looks like a loop to me, not a case statement.
It defines a single function called 'map', that takes two arguments.
first line says that map (with two arguments) if the second argument is an
empty list, return an empty list.
So, "map" is an operator, and "f" is the name of a function?
Map is a function that takes two arguments. 'f' is an argument to the
function 'map'. It is a variable that itself is a function type. Map is
defined using pattern matching. The implementation effectively tries each
pattern to see if it matches and uses the first definition that matches
(obviously it isn't implemented this way).
Probably not the best introduction to Haskell :-)
The second line says to split apart the first item from the rest of the
list, call f with that argument, and stick that on the beginning of a new
list which recursively invokes map on the rest of the list.
I actually preferred lisp's CDR and CAR to this implicit breaking of
lists.
List deconstruction by patterns is a lot more readable than things like
cddadr.
foo (a:b:c:d:r) = ...
a, b, c, d are the first 4 elements of the list. r is the rest of the
list.
map :: (a -> b) -> [a] -> [b]
All from just those two lines? Doesn't it need to know about the
definition of 'f' first?
Nope. 'f' is an argument to the function. It isn't defined anywhere. It
is able, from the use, to determine that the type of 'f' must be a function
that takes an argument of some arbitrary type and returns an argument of a
possibly different type.
which basically means the first argument is a function taking some type
'a', and returning some type 'b'. The second argument is a list of type
'a', and the function returns a list of type 'b'. Map doesn't care what
'a' and 'b' are, but for a given inference, all of the 'a's must map to the
same type, and all of the 'b's to the same type.
...yup, okay. Because f is invoked on the head of the list every time, it
has a consistent input. And because the new list is made up of invoking f
each time, you get the same output type from f, so it's all the same type.
What if you had (guessing wildly at syntax):
map f g [] = []
map f g (x:r) = ((x even ? f x) (x even not ? g x)) : (map f g r)
Ok, I'm guessing you want to invoke f on the even values, and g on the odd,
right?
map f g [] = []
map f g (x:r) = (if (even x) then (f x) else (g x)) : (map f g r)
(I've put in some extra parens)
so now we have to have some already existing function called 'even', which
conveniently exists. Numbers are a little complicated in haskell, but
basically since we are passing 'x' as an argument to 'even' which only
takes numbers, the type of 'x' will be constrained to numbers. This
constrains the type of 'r', since lists are always homogeneous. The
inference also applies to f and g, which will be constrained to take some
numeric type.
It doesn't know anything about the return types of f and g, except that
they must both return the same type. So, it'll give a type signature like:
map :: (Integral a) => (a -> b) -> (a -> b) -> [a] -> [b]
In fact, an example of this (renaming 'map' to foo, since map is already
taken)
inc x = x + 1
dec x = x - 1
> foo inc dec [1..10]
[0,3,2,5,4,7,6,9,8,11]
map (f,g) [] = []
map (f,g) (x:r) = (f x) : (map (g,x) r )
Anyway... I suspect you'd either have to coerce f and g to have the same
return types (walk your graph), or you'd get a potential conflict here.
Yes? No? Almost? Off in left field?
I'm not quite sure what you're trying to say, though. I don't think this
could be type resolved. (BTW, you can say map f g (x:r), although
putting the (f,g) in a pair does work).
So, 'f' will be called with the first element of the list. 'g' will be
called with the second element. Then the first element of the list will be
called with the third element of the list, and so on. I'm not sure if
that's what you meant, but I don't think it is typesound.
In fact, let's give it to haskell:
Occurs check: cannot construct the infinite type: t = t -> a
Expected type: (t -> a, t) -> [t] -> [a]
Inferred type: (t -> a, t -> a) -> [t] -> [a1]
In the second argument of `(:)', namely `(map (g, x) r)'
In the expression: (f x) : (map (g, x) r)
So, yes, it isn't possible to make a type which is a function that takes
it's own type.
Dave
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
