-- This Curry example program discusses some aspects of Curry's type system.

-- Curry is a strongly typed language, i.e., each entity has a type
-- which is checked at compile time to avoid run-time errors due to
-- incompatible types.
-- Types annotations are introduced by a double colon.
-- For instance, the type of a function to compute the length
-- of a string (a list of characters) is declared as follows:
strLen :: [Char] -> Int
strLen []     = 0
strLen (c:cs) = 1 + strLen cs

-- Type annotations need not be written by the programmer
-- since they are automatically inferred by the compiler.
-- Actually, the inferred types are sometimes more general
-- as intended by the programmer. For instance, we could
-- also define the function to compute the length without a
-- type annotation:
length []     = 0
length (x:xs) = 1 + length xs

-- The type inferred for `length` is polymorphic, i.e.,
-- parametric over the type of list elements:
--
--     length :: [a] -> Int

-- Nevertheless, it is a good programming style to write down
-- the types of the top-level functions to provide some
-- minimal documentation or specification of their intended use.
-- Still, type inference is useful for locally defined entities,
-- as in the following definition of sorting a list by repeated
-- sorted insertion of the elements into the already sorted part
-- of the list:
iSort :: [Int] -> [Int]
iSort []     = []
iSort (x:xs) = insert (iSort xs)
 where
  insert []                 = [x]
  insert (y:ys) | x <= y    = x : y : ys
                | otherwise = y : insert ys

-- Sort some list of integers:
main = iSort [3,1,6,2,5,4]

-- Final note: the type system of Curry is quite general.
-- If you delete the type annotation of `iSort`, then you could
-- also sort lists of characters since Curry infers a more general
-- type for `iSort`: just replace the `main` definition above by
--
--     main = iSort "Hello World!"