HASKELL LISTS

REVISED: Saturday, February 3, 2024

Haskell Lists.

I.  HASKELL NUMERIC AND CHARACTER LISTS

The Data.List module is the home of all standard list functions.

Prelude>  :module +Data.List

Prelude>

Prelude>  "U" `isPrefixOf` "USA" -- isPrefixOf function matches at the beginning of a list.
True
it :: Bool
Prelude>

Prelude>  "S" `isInfixOf` "USA"   -- isInfixOf function matches anywhere in a list.

True

it :: Bool

Prelude>

Prelude>  "A" `isSuffixOf` "USA" -- isSuffixOf function matches at the end of a list.
True
it :: Bool
Prelude>

Prelude>  :type isPrefixOf
isPrefixOf :: Eq a => [a] -> [a] -> Bool
Prelude>

Prelude>  :type isInfixOf
isInfixOf :: Eq a => [a] -> [a] -> Bool
Prelude>

Prelude>  :type isSuffixOf
isSuffixOf :: Eq a => [a] -> [a] -> Bool
Prelude>    

A list can be of any length.

In Haskell, lists are what arrays are in most other languages. 

[]  pronounced "nil" is an empty list.

Prelude> :type []
[] :: [t]
Prelude>

Haskell uses pattern matching to tell the compiler how to process data.

The module shown below has two patterns for the compiler to choose from. The first pattern is myMod [] and the second pattern is myMod (x:xs). The compiler makes a choice between the two patterns based on the contents of the function myMod argument. If the argument is an empty list [] the compiler chooses the myMod [] pattern. If the argument is a singleton list [x] or a list of [xs] the compiler chooses the myMod (x:xs) pattern. By convention, list arguments usually have an s suffix on their name; e.g., [xs] for a list of xs, or  [[xss],[]] for a list of lists and so forth.

The function syntax is as follows:

<function name> <function arguments> = <return values>

error is a Prelude function that allows the programmer to code a message to be printed when an exception error occurs. In the module shown below the programmer is telling the compiler that when myMod has the empty list [] as an argument to print the exception error message "Empty list!". The programmer can choose any message to be printed as long as the message in enclosed in double " " marks.

Module:

module MyMod where  -- All module names; i.e., MyMod start with a capital letter.

myMod :: [t] -> [t]  -- Function signature.
myMod [] = error "Empty list!"  -- When argument is an empty list [], prints exception error message.
myMod (x:xs) = xs  -- Pattern which returns xs.

GHCi:

Prelude>  :load MyMod
[1 of 1] Compiling MyMod               ( MyMod.hs, interpreted )
Ok, modules loaded: MyMod.
Prelude>

Prelude>  myMod []
*** Exception: Empty list!
Prelude> 

Prelude>  myMod [1,2,3,4,5,6,7,8,9,10]
[2,3,4,5,6,7,8,9,10] -- Notice the compiler return xs which is the tail of the list.
Prelude>  

A singleton pattern is a design pattern that restricts the instantiation of a class to one object. 

[a] is a singleton list (a:[]).

Prelude>  :t (:[])  -- Rotate (:[]) 90 degrees to the right and you see the head of a robot.
(:[]) :: a -> [a]
Prelude>  

[l, 2]  is read, "list with elements of type integer."

Prelude> :type [1,2]
[1,2] :: Num t => [t]
Prelude>

=> reads, "implies". The way to read the above is to say, “t being an instance of Num implies a list [t] of t's.”

[True,False]  is read, "a list with elements of type Boolean."

Prelude> :type [True,False]
[True,False] :: [Bool]
Prelude>

[(1, 2), (2, 3)]  is read, "a list of tuples of Integers".

Prelude> :type [(1,2),(2,3)]
[(1,2),(2,3)] :: (Num t1, Num t) => [(t, t1)]
Prelude>

[[1, 2], [2, 3, 4]]  is read, "a list of Integer-lists".

Prelude> :type [[1,2],[2,3,4]]
[[1,2],[2,3,4]] :: Num t => [[t]]
Prelude>

A. HASKELL LISTS FROM GIVEN ELEMENTS

The value to the left of the :,  pronounced "cons" for construct, is placed as the first element of the list. cons is another word for :. In lists, : is actually a constructor that takes a value and another list, and returns a list.

Prelude>  :type (:)
(:) :: a -> [a] -> [a]
Prelude>

Prelude> 1 : 2 : 3 : []
[1,2,3]
it :: Num a => [a]

Prelude>

We can also use the Prelude foldr function to show an example of the identity function. 

Prelude>  let myId = foldr (:) []
Prelude>

Prelude>  :type myId
myId :: [a] -> [a]
Prelude>

Prelude>  myId [1,2,3]
[1,2,3]
it :: Num a => [a]
Prelude>  

These examples are really singly-linked lists, and not arrays. Haskell does not have array primitives.

Prelude> 4: 5 : 6 : []
[4,5,6]
it :: Num a => [a]

Prelude>

Prelude> "1" : "2" : "3" : []
["1","2","3"]
it :: [[Char]]

Prelude>

Prelude> "4": "5": "6": []

["4","5","6"]

it :: [[Char]]

Prelude>

B. COMBINING HASKELL LISTS

Prelude> [1,2,3] ++ [4,5,6]     -- ++ is pronounced, "append"; and concatenates two lists.
[1,2,3,4,5,6]
it :: Num a => [a]

Prelude>

Prelude> ["1","2","3"] ++ ["4","5","6"]
["1","2","3","4","5","6"]
it :: [[Char]]

Prelude>

Prelude>  :type (++)   -- :t is the same as :type.

(++) :: [a] -> [a] -> [a]

Prelude>

Prelude>  concat [ ["1","2","3"] , ["4","5","6"] ]

["1","2","3","4","5","6"]   -- Prelude concat function removes one level of nesting; i.e., the inner square brackets.
it :: [[Char]]

Prelude>  

Prelude>  :type concat
concat :: [[a]] -> [a]
Prelude>

module MyApp2List where

(++)              :: [a] -> [a] -> [a]
[]        ++ ys = ys
(x:xs) ++ ys = x : (xs ++ yx)

II. ACCESSING HASKELL SUBLISTS

Strings are lists of characters; therefore, you can use list functions on strings.

A. ACCESSING THE FIRST ELEMENT OF A LIST

To access the first element of a list, we use the Prelude head function.

Prelude> :type head
head :: [a] -> a
Prelude>

a is the type variable. We can read the signature as “takes a list, all of whose elements have some type a, and returns a value of the same type a”.

Prelude> let ls = ["1","2","3","4","5","6"]  -- ls is immutable, it never changes.
Prelude>

Prelude> head ls -- Returns a new list containing the first list element of ls.

"1"
it :: [Char]

Prelude>

head is what is known as a partial function. There are certain inputs, i.e., empty list [], for which head will crash. 

Prelude>  head []

*** Exception: Prelude.head: empty list  -- Calling an exception or an error does not qualify as returning a value!

Prelude>  

Functions which have certain inputs that will make them recurse infinitely are also called partial. Functions which are well-defined on all possible inputs are known as total functions. It is good Haskell practice to avoid partial functions. Other partial Prelude functions include tail, init, last, and (!!).

Shown below is the Prelude tail function, which returns all but the head of a list.

Prelude> let ls =  ["1","2","3","4","5","6"]
Prelude>

You have to add ls to local memory because when you do the :load MyTail all local memory is erased.

Prelude> tail ls  -- Removes the first list element from list ls.

["2","3","4","5","6"]  -- Haskell creates a new list; this is not the original ls list.

it :: [[Char]]

Prelude>

Writing your own version of Prelude functions helps you learn Haskell. For example, the following myTail is a version of Prelude Tail.

Module:

module MyTail where  -- Module names; e.g., MyTail must always start with capital letter.

myTail            :: [t] -> [t]  -- Function names; e.g., myTail must always start with lower case letter.
myTail        [] = error "Empty list!"
myTail (x:xs) = xs

GHCi:

Prelude> :load MyTail
[1 of 1] Compiling MyTail               ( MyTail.hs, interpreted )
Ok, modules loaded: MyTail.
Prelude>

Prelude> let ls =  ["1","2","3","4","5","6"]

Prelude>

You have to add ls to local memory because when you do the :load MyTail all local memory is erased.

Prelude>  myTail ls
["2","3","4","5","6"]  -- The list returned by myTail function body is a copy of ls.
Prelude>  

Prelude> ls
["1","2","3","4","5","6"] -- Original ls is immutable; therefore, does not change.
Prelude>

B. ACCESSING THE LAST ELEMENT OF A LIST

Prelude function last, returns the very last element of a list.

Prelude> :type last
last :: [a] -> a
Prelude>

Prelude> last ls

"6"
it :: [Char]

Prelude>

Prelude> ls
["1","2","3","4","5","6"]  -- ls is immutable; therefore,  ls does not change.
Prelude>

Module:

module MyLast where

myLast            :: [t] -> t
myLast        [] = error "Empty list!"
myLast      [x] = x
myLast (x:xs) = myLast xs

GHCi:

Prelude>  :load MyLast
[1 of 1] Compiling MyLast               ( MyLast.hs, interpreted )
Ok, modules loaded: MyLast.
Prelude>

Prelude>  let ls = ["1","2","3","4","5","6"]
Prelude>

Prelude>  myLast ls
"6"

Prelude>

C. ACCESSING AN ELEMENT AT A GIVEN INDEX

If you want to get an element out of a list by index, use !! pronounced index.

Prelude> :type (!!)

(!!) :: [a] -> Int -> a
Prelude>

Prelude> ["1","2","3","4","5","6"] !! 3

"4"

it :: [Char]

Prelude>

There are both "zero based indexes" and "one based indexes". Zero based indexes start with zero. One based indexes start with one. Haskell uses zero based indexes for lists. Therefore, in our example above; index 0 would return 1, index 1 would return 2, index 2 would return 3, and index 3 would return 4.

D. ACCESSING THE FIRST N ELEMENTS

Prelude> :type take
take :: Int -> [a] -> [a]
Prelude>

The -> is right associative; therefore, take gives type Int to a function.

take :: Int -> ([a] -> [a])

The function take takes one argument, an Int, and returns another function ([a] -> [a]). That other function also takes one argument, a list [a] , and returns a list [a] of the same type as its result.

The take function has two arguments: an integer n, and a list ls; and produces the first n elements of ls. By convention a list is written ls and a list of lists would be written lss each list argument with a s suffix.

Prelude> take 4 ["1","2","3","4","5","6"]
["1","2","3","4"]
it :: [[Char]]

Prelude>

Prelude>  takeWhile (<= 5) [1..]
[1,2,3,4,5]
Prelude>  

Module:

module MyTake where

myTake                :: (Ord a, Num a) => a -> [t] -> [t]
myTake n _
      | n <= 0         = []                                    -- Checking for negative numbers.
myTake _ []         = []                                    -- Checking for empty list.
myTake n (x:xs)  = x:myTake (n-1) xs  -- Checking all other cases.

GHCi:

Prelude>  :load MyTake
[1 of 1] Compiling MyTake               ( MyTake.hs, interpreted )
Ok, modules loaded: MyTake.

Prelude>

Prelude>  myTake (-5) [1,2,3,4,5,6]
[]
Prelude>

Prelude>  myTake 5 []
[]
Prelude>

Prelude>  myTake 5 [1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5]
Prelude>  

E. ACCESSING THE LAST N ELEMENTS

Prelude> :type reverse
reverse :: [a] -> [a]
Prelude>

Prelude> reverse . take 4 . reverse $ ["1","2","3","4","5","6"]
["3","4","5","6"]
it :: [[Char]]

Prelude>

The dot . is the function composition operator, dot is read as, "after". The dot . operator has very high precedence, surpassed only by function application.

Function composition is the act of pipelining the result of one function, to the input of another, creating an entirely new function. This can be done with any two functions, where the argument type of the first is the return type of the second.

$ is pronounced, "apply". When a $ is encountered, the expression on its right is applied as the parameter to the function on its left.

F. ACCESSING THE N ELEMENTS STARTING FROM INDEX M

Prelude> :type drop
drop :: Int -> [a] -> [a]
Prelude>

Prelude> take 4 $ drop 1 ["1","2","3","4","5","6"]
["2","3","4","5"]
it :: [[Char]]

Prelude>

module Drop where
drop                       :: Int -> [a] -> [a]
drop 0         xs       = xs
drop (n+1) []        = []
drop (n+1) (_:xs) = drop n xs

G. SPLITTING A STRING INTO A LIST OF WORDS

Prelude> :type words
words :: String -> [String]
Prelude>

Prelude> words "Mary had a little lamb."
["Mary","had","a","little","lamb."]
it :: [String]

Prelude>

Prelude>  unwords ["Mary","had","a","little","lamb."]

"Mary had a little lamb."

it :: String

Prelude>  

H. SPLITTING A LIST INTO TWO PARTS

Prelude> :type splitAt
splitAt :: Int -> [a] -> ([a], [a])
Prelude>

Prelude> splitAt 12 "abcdefghijklmnopqrstuvwxyz"
("abcdefghijkl","mnopqrstuvwxyz")
Prelude>
Prelude> splitAt 12 ['a'..'z']
("abcdefghijkl","mnopqrstuvwxyz")

Prelude>

I. LENGTH OF A LIST

The length function tells us how many elements are in a list.

Prelude> :type length
length :: [a] -> Int
Prelude>

Prelude> length "abcdefghijklmnopqrstuvwxyz"

26
Prelude> length ['a'..'z']
26

Prelude>length [1..10]

10

Prelude>

module Length where

length            :: [a] -> Int
length        [] = 0
length (_:xs) = 1 + length xs
{-
length maps the empty list to 0, and any non-empty list to
the successor of the length of its tail.
-}

Prelude> :{
Prelude| len [] = 0
Prelude| len (_:xs) = 1 + len xs
Prelude| :}
Prelude> len [1,2,3,4,5,6,7,8,9,10]
10
Prelude>

Prelude> let myLength = sum . map (\_ -> 1)
Prelude> myLength [1,2,3,4]
4

J. REVERSE A LIST

Prelude> :type reverse
reverse :: [a] -> [a]
Prelude>

Prelude> reverse [1,2,3]

[3,2,1]
it :: Num a => [a]
Prelude>

module Reverse where

reverse            :: [a] -> [a]
reverse        [] = []
reverse (x:xs) = reverse xs ++ [x]
{-
reverse maps the empty list to the empty list
and any non-empty list to the reverse of its tail
appended to its head.
-}

The process of interpreting code by substituting equals-for-equals is known as equational reasoning. For example, with equational reasoning we can compute the reverse of 1, 2, 3 as follows:

reverse [1,2,3]
=
reverse [2,3] ++ [1]
=
(reverse [3] ++ [2]) ++ [1]
=
((reverse [] ++ [3]) ++ [2]) ++ [1]
=
(([] ++ [3]) ++ [2]) ++ [1]
=
[3,2,1]

K. APPLY A FUNCTION TO EACH ELEMENT IN A LIST

The higher-order library function called map applies a function; for example, (5*) to every element of a list.

Prelude> :type map
map :: (a -> b) -> [a] -> [b]
Prelude>

Prelude> map (5*) [1, 2, 3, 4, 5, 6]
[5, 10, 15, 20, 25, 30]
it :: Num b => [b]
Prelude>

Using (5*) is called sectioning notation which is the same as using an anonymous function fiveX = \x -> x * 5.

Prelude>  let fiveX = \x -> x * 5
Prelude>

Prelude>  fiveX 2
10
Prelude>

Prelude>  :type fiveX
fiveX :: Num a => a -> a
Prelude>  

The map function defined using list comprehension:

map f xs = [f x | x <- xs]

The map function defined using recursion:

map f []        = []
map f (x:xs) = f x : map f xs

L. FILTER A LIST

Prelude> :type filter
filter :: (a -> Bool) -> [a] -> [a]
Prelude>

filter cannot add elements; it can only remove them. When we filter we are choosing whether to keep an element of a list, depending on whether or not a particular predicate holds. A predicate is a function of type Int -> Bool which returns True for those elements which should be kept, and False for those which should be discarded.

filter returns a list constructed from members of a list, the second argument, fulfilling a condition given by the predicate, the first argument.

Prelude> filter (>5) [1, 2, 3, 4, 5, 6, 7, 8]
[6, 7, 8]
it :: (Ord a, Num a) => [a]
Prelude>

Filter defined using list comprehension:

filter p xs = [x | x <- xs, p x]

Filter defined using recursion:

filter p []        = []
filter p (x:xs)
    | p x            = x : filter p xs
    | otherwise = filter p xs

M. FOLD A LIST

Any function that traverse a list from left to right or right to left, one element by element, and accumulates a result, can be implemented with a fold.

Prelude> :type foldl

foldl :: (b -> a -> b) -> b -> [a] -> b

Prelude>

foldl takes a function which turns a b and a b into a b, an initial value of type b and a list of as. It produces a b.

Prelude> :type foldr

foldr :: (a -> b -> b) -> b -> [a] -> b
Prelude>

fold takes in a function and folds it in between the elements of a list. foldr folds from the right and foldl folds from the left.

sum       = foldr (+)   0

product = foldr (*)    1

or          = foldr (||)   False

and        = foldr (&&) True

Foldr defined using recursion and the above notation:

f = (+)

v = 0

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v []        = v
foldr f v (x:xs) = f x (foldr f v xs)

The compiler is able to turn most recursions into loops. This is called tail recursion optimization, where the recursive call at the very end of a function is simply turned into a goto to the beginning of the function. 

Prelude> import Data.Foldable

Prelude>

Prelude> Data.Foldable.foldl (+) 0 [1..5]     -- Zero indexed, 0 starting point.
15
it :: (Num a, Enum a) => a
Prelude>

This is the same as:

0 + 1 + 2 + 3 + 4 + 5

which equals 15.

This is the same as:

sum2            :: Num a => [a] -> a
sum2 []        = 0
sum2 (x:xs) = x + sum2 xs

Prelude>  :load sum2
[1 of 1] Compiling Main             ( sum2.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Prelude>  sum2 [0,1,2,3,4,5]
15
Prelude>

sum2 [0,1,2,3,4,5]
=
foldr (+) 0 [0,1,2,3,4,5]
=
foldr (+) 0 (0:(1:(2:(3:(4:(5:[]))))))  -- fold right
=
0+(1+(2+(3+(4+(5+0)))))
=
6

N. ZIP A LIST

As shown below zip transposes a pair of lists ([a] , [b]) into a list of pairs [(a, b)] :

Prelude> :type zip
zip :: [a] -> [b] -> [(a, b)]
Prelude>

The library function zip produces a new list by pairing successive elements from two existing lists until either or both are exhausted.

Prelude> zip [1,2,3] [9,8,7]
[(1,9),(2,8),(3,7)]
it :: (Num b, Num a) => [(a, b)]
Prelude>

Module:

module MyZip where

myZip                       :: [a] -> [b] -> [(a,b)]     -- Function signature.
myZip  []  _              = []                                           -- [a] becomes empty first.
myZip  _   []             = []                                           -- [b] becomes empty first.
myZip (x:xs) (y:ys) = (x,y) : myZip xs ys             

GHCi:

Prelude>  :load MyZip
[1 of 1] Compiling MyZip               ( MyZip.hs, interpreted )
Ok, modules loaded: MyZip.
Prelude>

Prelude>  let ls1 = ["1", "2", "3"]
Prelude>

Prelude>  let ls2 = ["4", "5", "6"]
Prelude>

Prelude>  myZip ls1 ls2
[("1","4"),("2","5"),("3","6")]
Prelude>  

O. ZIPWITH A LIST

Prelude> :type zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude>

zipWith makes a list whose elements are calculated from a function and the elements of input lists occurring at the same position in both lists.

Prelude> zipWith (+) [1,2,3] [3,2,1]

[4,4,4]
it :: Num c => [c]
Prelude>

P. liftM

Prelude>  import Control.Monad

Prelude>

liftM promotes a function to a monad.

Prelude> :type liftM
liftM :: Monad m => (a1 -> r) -> m a1 -> m r
Prelude>

Prelude> import Control.Monad
Prelude>

"Copy Paste" the following script into your text editor, and "File, Save As" MaryTxtFile.txt in your working directory.

Mary had a little lamb,
its fleas were white as snow.
And everywhere that Mary went,
its fleas were sure to go.

Prelude>  :cd C:\Users\Tinnel\Haskell2024\
Prelude>

Prelude> liftM lines (readFile "MaryTxtFile.txt")
["Mary had a little lamb,","its fleas were white as snow.","And everywhere that Mary went,","its fleas were sure to go."]
it :: [String]
Prelude>

Q. LIST COMPARISONS

Lists can be compared if the elements within the lists can be compared. When using <, <=, >, and >= to compare lists, they are compared in lexicographical order. First the heads are compared. If they are equal then the second elements are compared, etc.

R. LIST COMPREHENSIONS

Let S be a set,  ∀ be for every, ∈ be is an element of, and p(x) be a predicate.

Mathematically we can write the following statement.

∀x∈S, p(x)

For every x such that x is an element of the set S and satisfies the predicate p(x).

We write the above in Haskell as follows:

[ x | x <- S,  p x ]

In Haskell <- is pronounced "drawn from" and p x is called a condition, or "predicate".

Below, the function x which satisfies the predicate x+5  is drawn from the set [1,2,3].

Prelude>  [ x+5 | x <- [1,2,3] ]
[6,7,8]
it :: Num t => [t]
Prelude>

Prelude>  [ x | x <- [2..10], 10 `mod` x  == 0]
[2,5,10]
Prelude>

Prelude>  [ team ++ " " ++ player | 
             team   <- ["red", "blue"], 
             player <- ["soldier", "pyro", "scout"] ]  -- Surprised? Try it.
["red soldier","red pyro","red scout","blue soldier","blue pyro","blue scout"]
it :: [[Char]]
Prelude> 

The following is accepted by Prelude as shown above because it is one single line of code:

[ team ++ " " ++ player | team   <- ["red", "blue"], player <- ["soldier", "pyro", "scout"] ] 

List comprehensions are used for building more specific lists out of general lists.

S is a set.
∈ is an element of.
ℕ is a set of all natural numbers.

S = { x * 3 | x ∈ ℕ, (x * 3) ≦ 51 }

Prelude>  [x*3 | x <- [0..], x*3 <= 51]  
[0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51Interrupted.
Prelude>

In the example above GHCi will stop processing at 51. There is a tool bar at the top of the GHCi window. Select Actions in the GHCi tool bar, and then select Stop; or press Ctrl+C to interrupt processing and to return to the Prelude> prompt.

S = { x * 3 | x ∈ [12..20], (x * 3) ≦ 51 }

Prelude> [x*3 | x <- [12..20], x*3 <= 51]  
[36,39,42,45,48,51]
it :: (Ord t, Num t, Enum t) => [t]
Prelude>

The part before the pipe |, is the output function x*3. x is drawn from the input set of 12 to 20. For every element in 12..20 that we have bound to x we get that element x multiplied by 3 if it satisfies the condition, predicate, of being <= 51.

List comprehensions are an expressive shorthand for building computations on lists.

S. LIST DIFFERENCE \\ OPERATOR

Prelude> :type (\\)

(\\) :: Eq a => [a] -> [a] -> [a]
Prelude>

The list difference \\ operator takes two lists, goes through the second and for each item, removes the first instance of the same item from the first list.

Prelude> import Data.List
Prelude>

Prelude> [1..10] \\ [2, 3, 5, 8]
[1,4,6,7,9,10]
it :: (Num a, Eq a, Enum a) => [a]
Prelude>

[1, 2,3,4,5,6,7,8,9,10]        -- First list [1..10].

[    2,3,    5,       8           ]       -- Second list.

[1,      4,   6,7,   9,10]

T. NUB

nub, eliminates all duplicate elements from a list.

Prelude>  :type nub
nub :: Eq a => [a] -> [a]

Prelude>

Prelude>  import Data.List
Prelude>

Prelude>  nub [1,1,2,2,3,3,4,4,5,5]
[1,2,3,4,5]
Prelude>

U. INIT

init, returns a list of all but the last element of its input.

Prelude>  :type init

init :: [a] -> [a]

Prelude>

Prelude>  :info init

init :: [a] -> [a] -- Defined in `GHC.List'

Prelude>

Prelude>  init "hello"

"hell"

it :: [Char]

Prelude>  

Module:

module MyInit where

myInit            :: [t] -> [t]
myInit        [] = error "Empty list!"
myInit      [_] = []
myInit (x:xs) = x:myInit xs

GHCi:

Prelude>  :load MyInit
[1 of 1] Compiling MyInit              ( MyInit.hs, interpreted )
Ok, modules loaded: MyInit.

Prelude>  let ls = ["1","2","3","4","5","6"]

Prelude>

Prelude>  myInit ls

["1","2","3","4","5"]

Prelude>

Prelude>  myInit ["1"]

[]

Prelude>

Prelude>  myInit []

*** Exception: Empty list!

Prelude>

V. ELEM

elem is the list membership predicate, usually written in infix form, e.g., x `elem` xs.

Prelude>  :type elem
elem :: Eq a => a -> [a] -> Bool
Prelude>  

Prelude>  5 `elem`  [1,2,3,4,5]  -- Infix uses backticks ` not apostrophes '.
True
Prelude>

Module:

module MyElem where

myElem               :: Eq a => a -> [a] -> Bool
myElem _ []        = False
myElem e (x:xs)
        | e == x      = True
| otherwise = myElem e xs

GHCi:

Prelude>  :load MyElem
[1 of 1] Compiling MyElem               ( MyElem.hs, interpreted )
Ok, modules loaded: MyElem.
Prelude>

Prelude>  myElem 5 [1,2,3,4,5]
True
Prelude>

Prelude>  myElem 5 [1,2,3,4]
False
Prelude>

W. SORT

sort sorts a list.

Prelude>  :type sort

sort :: Ord a => [a] -> [a]

Prelude>

Prelude>  sort [4,3,6,9,1,2]

[1,2,3,4,6,9]

Prelude>

X. PRODUCT

Prelude> product [4,3,6,9,1,2]

1296
Prelude>

III. CONCLUSION

In this tutorial, you have received an introduction to Haskell lists.

IV. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

HASKELL INPUT AND OUTPUT (IO)

REVISED: Monday, October 21, 2024

Haskell Input and Output (IO).

Good Haskell style involves separating pure code from code that performs IO.

I.  HASKELL IMPORT

I am asking you to input the following imports so I can use them in examples "I. A." and "I. B." shown below. I also want to demonstrate the dangers of using imports without knowing their contents.

Prelude> import Control.Arrow

Prelude>

Prelude> import Control.Monad
Prelude>

Prelude> import Data.ByteString
Prelude>

Prelude> import Data.Char
Prelude>

Prelude> import Data.List 
Prelude>

Prelude> import System.IO  
Prelude>

Prelude> import System.Directory
Prelude>

Prelude> import System.Environment 
Prelude>

Prelude> import System.IO.Error
Prelude>

Prelude> import System.Random 
Prelude>

A. :SHOW IMPORTS

Prelude> :show imports
import Prelude -- implicit
import Control.Arrow
import Control.Monad
import Data.ByteString
import Data.Char
import Data.List
import System.IO
import System.Directory
import System.Environment
import System.IO.Error
import System.Random
:module +*Main -- added automatically
Prelude>

Notice Data.ByteString is in the above list of imports.

B. :MODULE -M

Where M is the name of the import you want to remove, imports can be removed from the current scope, using the syntax :module -M as shown below:

Prelude> :module -Data.ByteString
Prelude>

Prelude> :show imports
import Prelude -- implicit
import Control.Arrow
import Control.Monad
import Data.Char
import Data.List
import System.IO
import System.Directory
import System.Environment
import System.IO.Error
import System.Random
:module +*Main -- added automatically
Prelude>

Notice Data.ByteString is not in the above list of imports.

The full syntax of the :module command is: 

:module [+|-] [*]mod₁ ... [*]mod_n

Using the + form of the module command adds modules to the current scope, and - removes them.

You cannot add a module to the scope if it is not loaded.

II.  HASKELL "IO ACTIONS"

If you did:

Prelude> import Data.ByteString
Prelude>

Prelude> import System.IO
Prelude>

and did not do:

Prelude> :module -Data.ByteString
Prelude>

as shown above in I., you will receive an "ambiguous occurrence" error message from GHCi when you do the examples shown below. GHCi will not be able to determine which import you are referring to. Therefore, you have to be very careful when using multiple imports. It is a good idea to know everything contained in an import before you use it.

The GHCi prompt operates as if the lines were being typed into a do block in the IO monad.

Prelude> :type putStrLn

putStrLn :: String -> IO ()
Prelude>

putStrLn gives back nothing, ().

Prelude>  :t getLine

getLine :: IO String

Prelude>

getLine gives back a String to use. 

Prelude> :type readFile
readFile :: FilePath -> IO String
Prelude>

IO is Haskell’s way of representing that putStrLn and readFile are not really functions, in the pure mathematical sense, they are “IO Actions”. Typical actions include reading and setting global variables, writing files, reading input, and opening windows.

The -> drawn from notation is a way to get the value out of an action. The (), pronounced “unit”, is an empty tuple indicating that there is no return value from putStrLn. This is similar to "void" in Java or C.

If we are taking data out of an IO action, we can only take it out when we are inside another IO action. In other words, to get the value out of an IO action, you have to perform it inside another IO action by binding it to a name with the -> drawn from arrow function. Variables bound by the -> drawn from arrow function are lambda bound and are thus monomorphic. IO actions will only be performed when they are given the name of main or when they are inside a bigger IO action that was composed with a do block. Therefore, when you want to bind the results of IO actions to names, use the -> drawn from arrow function.

The only way to use things with an IO type is to combine them with functions using do notation which can include if/then/else and case/of. In a do expression, every line is a monadic value. We code do and then we lay out a series of steps, like we would in an imperative program chaining computations. Each of these steps is an IO action, a control flow expression. A statement is either an action, a pattern bound to the result of an action using <-, or a set of local definitions introduced using let. By putting them together with do syntax, we glue them into one IO action. do works with any monad, the action that we get has a type of IO (), because that is the type of the last IO action inside the do. When sequencing actions with do notation, each “bare” line, lines that do not have a <- in them, must have type IO ().

do can replace the  >> pronounced "then" operator.

Prelude> :type (>>)
(>>) :: Monad m => m a -> m b -> m b
Prelude>

We can use do syntax to glue together several IO actions into one.  The value from the last action in a do block is bound to the do block result.

You always do IO inside a do statement, using the IO monad. This way you are guaranteed that IO actions are executed in order.

$ is pronounced "apply." When a $ is encountered, the expression on its right is applied as the parameter to the function on its left. In other words the $ is the same as a ( and the closing ) is the end of the line. For example (1, 2, 3, 4) is the same as $ 1, 2, 3, 4

You cannot use $ if the closing ) would not appear at the end of the line.

A. REVIEW

First, we will review GHCi "ambiguous occurrence" error messages: 

Try doing the following examples. You will receive another GHCi "ambiguous occurrence" error message. The point I am repeatedly trying to make is you should understand the contents of imports before using them.

Exit out of GHCi and then reload GHCi. Use the following commands to see what you start out with in GHCi when it is first loaded.

Prelude>  :show

options currently set: +t   -- +t prints type after evaluation

base language is: Haskell2010

with the following modifiers:

  -XNoDatatypeContexts

  -XNondecreasingIndentation

GHCi-specific dynamic flag settings:

other dynamic, non-language, flag settings:

  -fimplicit-import-qualified

warning settings:
Prelude>

Prelude>  :show imports

import Prelude -- implicit

Prelude>  

Second, we will show a basic example of putStrLn:

Prelude> :{

Prelude| do {

Prelude| putStrLn "Hello, World!"

Prelude| }

Prelude| :}

Hello, World!

it :: ()

Prelude>

Third, we will show an example of using getLine and $ with putStrLn:

Prelude> :{
Prelude| let prRev = do {
Prelude|      inp <- getLine;
Prelude|      putStrLn $ reverse inp;
Prelude| }
Prelude| :}
Prelude| 
Prelude>

Prelude> :type prRev
prRev :: IO ()
Prelude>

Prelude> prRev

Hello, World!

!dlroW ,olleH

Prelude>

B. OUTPUT FUNCTIONS

These functions write to the standard output device, which is normally the user's terminal.

Prelude> import Data.Char
Prelude>

Prelude> :type print
print :: Show a => a -> IO ()
Prelude>

Prelude> :type putChar

putChar :: Char -> IO ()
Prelude>

The unit type (), which is similar to void in other languages, is used by actions which return no values.  return packs up a value into an IO box. <- extracts the value out of an IO box and is read as "comes from". In other words, return turns a value into an IO action and <- turns an IO action into a regular value.

"Copy paste" the following Haskell script into your text editor and "save as" TestReturn.hs  to your working directory:

-- TestReturn.hs

module TestReturn where

main = do putStrLn "Shall I quit the program? y/n"
          ans <- getLine
          if ans /= "y"
             then do putStrLn "Thank you! I enjoy working with you!"
                     main
             else do putStrLn "Nice working with you my friend! Happy trails, until we meet again!"
                     return ()  -- We created an IO that does not do anything so the program can exit.

As shown below, load the TestReturn program, then run the module TestReturn function main, in GHCi:

Prelude>  :load TestReturn
[1 of 1] Compiling TestReturn       ( TestReturn.hs, interpreted )
Ok, modules loaded: TestReturn.
Prelude>

Prelude>  main
Shall I quit the program? y/n
n
Thank you! I enjoy working with you!
Shall I quit the program? y/n
y
Nice working with you my friend! Happy trails, until we meet again!
it :: ()
Prelude>  

PS C:\Users\User\tinnel\Haskell 2024\newProjects> ghci

GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help

ghci> :load TestReturn.hs

[1 of 1] Compiling TestReturn       ( TestReturn.hs, interpreted )

Ok, one module loaded.

ghci> main

Shall I quit the program? y/n

n

Thank you! I enjoy working with you!

Shall I quit the program? y/n

y

Nice working with you my friend! Happy trails, until we meet again!

ghci>

putStrLn is a function that takes a single argument of type String and produces a value of type IO (). The IO () signifies an executable action that returns a value of type (). When we supply putStrLn with a String argument we get an executable IO action which will print the supplied String.

Prelude> :type putStr

putStr :: String -> IO ()
Prelude>

Prelude> putStr "Hello"
Helloit :: ()   -- Notice that two lines combine without a \n newline escape sequence!

Prelude> 

Prelude> putStr "Hello\n"

Hello   -- The \n newline escape sequence does a carriage return.
it :: ()Prelude>

Prelude> :type putStrLn

putStrLn :: String -> IO ()

Prelude>

Prelude> :type putStrLn "abcdefghijklmnopqrstuvwxyz"
putStrLn "abcdefghijklmnopqrstuvwxyz" :: IO ()
Prelude>

C. INPUT FUNCTIONS

These functions read input from the standard input device, which is normally the user's keyboard. 

Prelude> :type getChar

getChar :: IO Char
Prelude>

When the function getChar is invoked, it will perform an action which returns a character.

Prelude> :type getLine

getLine :: IO String
Prelude>

Should be read as, "getLine is an action that, when performed, produces a string".

Prelude> :type getContents

getContents :: IO String

Prelude>

Prelude> :type interact

interact :: (String -> String) -> IO ()
Prelude>

Prelude> :type readIO

readIO :: Read a => String -> IO a

Prelude>

Prelude> :type readLn

readLn :: Read a => IO a
Prelude>

Use let bindings to bind pure expressions, normal non-IO expressions, to names. For example:

Prelude> let y = 12
y :: Num a => a

Prelude>

Prelude> y

12
it :: Num a => a

Prelude>

As shown above, let bindings do not automatically print the value bound.

As shown below, when we type out a monadic IO action in GHCi and press Enter, the IO action will be performed:

Prelude> putStrLn "Hello, World!" 
Hello, World!
it :: ()

Prelude>

You are always writing code in the IO monad when you are using GHCi.  GHCi evaluates the IO action, then calls show on the IO action, and prints the string to the terminal using putStrLn implicitly. 

D. IO EXAMPLE 1

"Copy, Paste" the following program into your text editor and "File, Save As" Point.hs to your working directory:

-- Point.hs

module Point where

point :: IO (Char,Char)
point = do {  x <- getChar
                    ; getChar
                   ; y <- getChar
                   ; return (x,y)
                 }

Load Point.hs into GHCi as follows:

Prelude>  :load Point.hs
[1 of 1] Compiling Main             ( point.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

From GHCi call the Point.hs program as follows:

Prelude>  Point.hs
8  -- You will be prompted twice. At each prompt type an Integer then press Enter.
2
('8','2')  -- The output will return a tuple point :: IO (Char,Char).
Prelude>

PS C:\Users\User\tinnel\Haskell 2024\newProjects> ghci

GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help

ghci> :load Point.hs

[1 of 1] Compiling Point            ( Point.hs, interpreted )

Ok, one module loaded.

ghci> point

8

2

('8','2')

ghci> :quit

Leaving GHCi.

PS C:\Users\User\tinnel\Haskell 2024\newProjects> 

E. IO EXAMPLE 2

"Copy, Paste" the following program into your text editor and "File, Save As" Name.hs to your working directory:

-- Name.hs

module Name where

import Data.List()
import System.IO

main :: IO ()
main = do {  putStrLn "What is your name?"
                    ; yn  <- getLine

<- getline="" span="">                     ; putStrLn ("Hello " ++ yn ++ "!" ) 

                  }

Load Name.hs into GHCi as follows:

Prelude>  : load Name.hs
[1 of 1] Compiling Main             ( name.hs, interpreted )
Ok, one module loaded.
*Main>

From GHCi call the Name program as follows:

*Main>  main

What is your name?

Ron

Hello Ron!

*Main> 

PS C:\Users\User\tinnel\Haskell 2024\newProjects> ghci

GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help

ghci> :load Name.hs

[1 of 1] Compiling Name             ( Name.hs, interpreted )

Ok, one module loaded.

ghci> main

What is your name?

Ron

Hello Ron!

ghci> :quit

Leaving GHCi.

PS C:\Users\User\tinnel\Haskell 2024\newProjects> 

III. TEXT FORMAT

Keep lines to no more than 80 columns.

Do not use tabs.

Use CamelCase, do not use underscores.

Do not leave trailing white space in your lines of code.

Do not use braces and semicolons.

Use spaces for indenting.

Indent code blocks such as "let, where, do, and of" 4 spaces.

Indent "where" keyword 2 spaces.

Indent "where" definitions 2 spaces.

Indent "guards" 2 spaces.

IV. CONCLUSION

In this tutorial, you have received an introduction to Haskell input and output (IO).

V. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

HASKELL CONTROL STRUCTURE INTRODUCTION

REVISED: Friday, October 18, 2024

In this tutorial, you will receive an introduction to Haskell control structure.

I.  HASKELL CONTROL STRUCTURE

Without mutable variables, recursion is the only way to implement control structures.

A. HASKELL IF EXPRESSION

if condition
    then trueValue
    else  falseValue      

An expression is a piece of code that returns a value.

Haskell's "if expression" syntax is as follows:

if <condition> then <trueValue> else <falseValue>

<condition> is an expression which evaluates to a Boolean. If the <condition> is True then the <trueValue> is returned, otherwise the <falseValue> is returned.

In Haskell the else is mandatory.

The <trueValue> and <falseValue> must evaluate to the same type, which will be the type of the whole if expression.

Semicolons ; are not allowed in an if/then/else.

then and else must be indented deeper than the if statement.

The expressions after the then and else keywords are branches. The branches must have the same types. if expressions must also have the same types.

B. HASKELL GUARDS

Guards are a conditional expression mechanism in Haskell that allows you to select different expressions based on the truth value of certain conditions. They are often used to define functions with multiple cases or to implement complex logic in a concise and readable way.

| (guard boolean expression) = (guard function body expression)

A pattern can be followed by zero or more guards. Guards must be expressions of type Bool. A guard begins with a | pipe symbol, followed by the Boolean guard expression. Then followed by an = equal symbol, or -> to symbol if we are in a case expression. Then followed by the body to use if the Boolean guard expression evaluates to True. If a pattern matches, each guard associated with that pattern is evaluated, in the order in which the guards are written. If a Boolean guard expression evaluates to True, the body affiliated with that guard is used as the result of the function. If no guard evaluates to True, pattern matching continues to the next pattern.

The -> function arrow, read "to", can take two types; for example, Int and Bool and produce a new type Int -> Bool. The function arrow -> describes a function mapping from one type "to" another. 

When a guard expression evaluates to True, all of the variables mentioned in the pattern with which it is associated are bound and can be used.

Guards are a sequence of logical expressions used to choose between a sequence of results of the same type. If the first guard is True then the first result is chosen, otherwise, if the second guard is True then the second result is chosen, and so on.

Guards are a way of testing whether some properties of a value are True or False.

A guard is a Boolean expression. If it evaluates to True, the corresponding function body is used. If it evaluates to False, checking drops through to the next guard; etc.

Always use an otherwise guard as the last guard to have a match for all remaining cases.  otherwise is defined as otherwise = True and catches everything you did not code in the other guards.

Guards can be used instead of if-then-else expressions. Guards are evaluated in order and indicate various cases in the computation. The first guard that is True controls the result.

Module:

-- BooleanXY.hs

module BooleanXY where

booleanXY :: (Ord a1, Ord a, Num a1, Num a) => a -> a1 -> [Char]
booleanXY x y
    | x < 50       = "No"
    | y >= 50     = "Yes"
    | otherwise = "Maybe"

GHCi:

Prelude>  :load BooleanXY
[1 of 1] Compiling Main             ( BooleanXY.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Prelude>  :type booleanXY
booleanXY :: (Ord a1, Ord a, Num a1, Num a) => a -> a1 -> [Char]
Prelude>

Prelude>  booleanXY 10 50
"No"
Prelude>

Prelude>  booleanXY 50 50
"Yes"
Prelude>

Prelude>  booleanXY 60 30
"Maybe"
Prelude> 

PS C:\Users\User\tinnel\Haskell 2024\newProjects> ghci

GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help

ghci> :load BooleanXY.hs

[1 of 1] Compiling BooleanXY        ( BooleanXY.hs, interpreted )

Ok, one module loaded.

ghci> booleanXY 10 50

"No"

ghci>  booleanXY 50 50

"Yes"

ghci> booleanXY 60 30

"Maybe"

ghci> :quit

Module:

module MyReplicate where

myReplicate :: (Ord a, Num a) => a -> t -> [t]
myReplicate n x
        | n <= 0      = []
| otherwise = x:myReplicate (n-1) x

GHCi:

Prelude>  :load MyReplicate
[1 of 1] Compiling MyReplicate               ( MyReplicate.hs, interpreted )
Ok, modules loaded: MyReplicate.

Prelude>  myReplicate 5 47
[47,47,47,47,47]
Preluce>

Prelude>  myReplicate 47 5
[5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5]
Prelude>

Prelude>  myReplicate (-47) (-5)
[]
Prelude>

PS C:\Users\User\tinnel\Haskell 2024\newProjects> ghci

GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help

ghci> :load MyReplicate.hs

[1 of 1] Compiling MyReplicate      ( MyReplicate.hs, interpreted )

Ok, one module loaded.

ghci> myReplicate 5 47

[47,47,47,47,47]

ghci> myReplicate 47 5

[5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5]        

ghci> myReplicate (-47) (-5)

[]

ghci> :quit

Leaving GHCi.

PS C:\Users\User\tinnel\Haskell 2024\newProjects> 

II. CONCLUSION

In this tutorial, you have received an introduction to the Haskell control structure.

III. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.