9 Oct 11:11 2012

## Type of scramblings

Roman Cheplyaka <roma <at> ro-che.info>

2012-10-09 09:11:11 GMT

2012-10-09 09:11:11 GMT

I am reading through Oleg's "Eliminating translucent existentials"[1]. [1]: http://okmij.org/ftp/Computation/Existentials.html#eliminating-translucent He draws a distinction between forall a . [a] -> [a] and forall a . [a]^n -> [a] as types of "scramblings". This is something I'm struggling to understand. First of all, I think here we're talking about total functions, otherwise there's no point in introducing dependent types. There are of course more total functions of type `[a]^n -> [a]` than of type `[a] -> [a]`, in the sense that any term of the latter type can be assigned the former type. But, on the other hand, any total function `f :: [a]^n -> [a]` has an "equivalent" total function g :: [a] -> [a] g xs | length xs == n = f xs | otherwise = xs (The condition `length xs == n` can be replaced by a similar condition that also works for infinite lists.) The functions `f` and `g` are equivalent in the sense that for any list `xs` of(Continue reading)