The map function changes each element of a list while preserving its order and length. List concatenation removes one level of nesting. Currying changes a function on a pair into a function taking its two arguments separately; uncurrying reverses this conversion:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss
curry :: ((a, b) -> c) -> a -> b -> c
curry f x y = f (x, y)
uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (x, y) = f x yThese polymorphic type signatures impose no numerical, equality or ordering constraints: the definitions only inspect list or pair structure and apply a supplied function. In particular,The recursive equations describe the two possible list constructors, so they also explain how the empty case terminates each finite computation.
In the type signature
map :: (u -> v) -> [u] -> [v], the supplied function is concat :: [[a]] -> [a]. Type inference therefore identifies u with [[a]] and v with [a]. Consequently,map concat :: [[[a]]] -> [[a]]Thus is the principal type. For example,
map concat [[[1],[2,3]],[[4],[]]] gives [[1,2,3],[4]]: it concatenates each inner group, preserving the outermost grouping.Both uses of
x in this definition have the same monomorphic type within the body. Write x :: u -> v. The inner application x z forces z :: u and has type v; the outer application x (x z) forces v = u. Thus x :: u -> u. Finally, x (x z) is applied to y, so u must itself be a function type, say a -> b. This givesf :: ((a -> b) -> a -> b) -> a -> (a -> b) -> b
f x y z = x (x z) yThe principal type is thereforeThe argument
x transforms a function into another function of the same type. The body transforms z twice, then applies the resulting function to y; no recursive type equation is required.Represent Pascal's triangle by an infinite outer lazy list, each of whose elements is one finite row. Pad the preceding row with zero on its left and on its right, then add corresponding entries:
pascal :: [[Integer]]
pascal = iterate next [1]
where
-- Padding supplies the two boundary entries as well as the interior sums.
next :: [Integer] -> [Integer]
next row = zipWith (+) (0 : row) (row ++ [0])Here
iterate next [1] begins [[1],[1,1],[1,2,1],[1,3,3,1],...]. Every call to next receives a finite row, so its final zero is reachable. Lazy evaluation produces any requested finite prefix without trying to finish the infinite outer list.Indexing rows and columns from zero, Pascal's rule saysTake out-of-range binomial coefficients to be zero. The seed is the zeroth row, and the padded addition implements this identity at every position, including the two boundaries. Mathematical induction therefore proves every generated row correct. Using unbounded integers prevents overflow. Generating rows zero through takes arithmetic operations, with additional bit costs as the binomial coefficients grow.
Articles by others on the same topic
There are currently no matching articles.