Simple Question Again

Jay Cox sqrtofone@yahoo.com
Fri, 17 May 2002 09:46:43 -0500 (CDT)


On Fri, 17 May 2002, Jerry wrote:

> Hi, I'm sorry to bother everyone again with this simple append' stuff
> -- now this is something I _really_ don't understand:
> -- x is of type [a], [y] is of type [a], and isn't foldr (:) [a] [a]
> -- perfectly valid?!

:type foldr
forall a b. (a -> b -> b) -> b -> [a] -> b

now foldr is used with (:) which has type a -> [a] ->[a]

so, to find the type of foldr (:)
the type (a-> b -> b) must be unified with (:):: c->[c] -> [c]

therefore, (replacing a with c and b with [c])
foldr (:) :: [c] -> [c] -> [c]

which is what you expected. however, you forgot.

1) append' :: [[a]] -> a -> [[a]]
2) append' [] y = [[y]]
3) append' (x:xs) y =
4)     case xs of [] -> foldr (:) [y] x
5)                (z:zs) -> (init (x:xs)) ++ [(last xs)++[y]]

in "case of [] -> foldr (:) [y] x",

foldr (:) [y] x :: [c], the same type as x.
but append' works on lists of type [[c]] adds a element of type c and
returns something of type [[c]], as you have declared in the type
declaration of append'. so, what is the real problem?
the type given by foldr (:) [y] x :: [c] doesn't match the resultant type
of append', namely [[c]]

Also, another good thing to check is that all branches of a case
statement have the same type.  If
something x =case x of True -> 3; False -> "lala"
could compile, what would be it's type??

(Hint, if you come from the dynamically typed world and do want to do
something of the sort, there is the Either type.
case x of True -> Left 3; False -> Right "lala"

Jay Cox