THERE ARE MANY WAYS TO WRITE HASKELL PROGRAMS

REVISED: Tuesday, February 13, 2024

1. INTRODUCTION

There are many ways to write Haskell programs. The following are just a few of the many ways you can use Haskell to solve problems and present information with batch and interactive programs.

2. BATCH PROGRAMS

Firstly, you can write Haskell pure functions also called batch programs that have no side effects. Batch programs are programs that do not need to interact with the user while they are running. Batch programs take all their inputs at the start of the program and give all their outputs at the end of the program. Batch programs are written with functions that do not interact with their environment.

When programming first started many programs were batch programs which were run in computer centers far removed from the users who would use the output. Batch programming was well suited for payroll, inventory, accounts receivable, accounts payable, personnel, and in general most business applications. Many batch programs are still used today because they lend themselves to time cut offs such as the end of the month, the end of a payroll period, or the end of any accounting period of time.

3. INTERACTIVE PROGRAMS

Secondly, you can write Haskell impure functions also called interactive programs that do have IO side effects. Interactive programs are programs that do need to interact with the user while they are running. Interactive programs read from the keyboard and write to the screen as the program is running allowing the user to control input and output. These programs are normally run at the users location instead of an off site computer center. Interactive Haskell programs can be written in many ways including stream-based interaction, the interact function, and monads.

3.1. STREAM-BASED

Early versions of Haskell used stream-based interaction as the main method of interacting with the outside world. You can think of a stream as a continuing sequence of elements bundled in chunks. Stream processing applications are very important in our society. We want to know information the instant information is created. News of world events, changes in the stock market, political decisions which could start or stop a war are all things we want to know the moment they occur. 

3.2. INTERACT FUNCTION

The interact function signature is:

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

The following module uses the interact function which is a function that passes the entire input as a giant string to a function of your choice, then prints the returned string to standard output.

module InteractHaskell where

import Data.Char (toUpper)

main :: IO ()
main = interact upperCase

upperCase :: String -> String
upperCase = map toUpper

The output from GHCi is as follows:

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

Prelude>  upperCase "summer in the sun is lots of fun."
"SUMMER IN THE SUN IS LOTS OF FUN."
Prelude>  

3.3. IO ACTION MONADS

IO action monads have evolved into being the currently most often choice for writing Haskell programs. Three IO action primitives are getChar, putChar, and return. Some very basic IO action monad examples are shown below.

3.3.1. INPUT:

getChar :: IO Char           -- IO action primitive that reads a single Char from the terminal.
getLine :: IO String          -- IO action that reads a single String from the terminal.

3.3.2. OUTPUT:

putChar :: Char -> IO ()   -- IO action primitive that prints a single Char to the terminal.
putStr :: String -> IO ()    -- IO action that prints a single String to the terminal.

print :: Show a => a -> IO ()
putStrLn :: String -> IO ()

return :: Monad m => a -> m a  -- Monad is an IO action primitive that returns any type.

3.3.3. IO ACTION MONAD EXAMPLES

A sequence of actions can be combined as a single composite action using the keyword do.

Four examples of the above IO action monads using do are as follows:

3.3.3.1. Example 1

Module:

module ExOne where

ex1a :: IO ()
ex1a = do putStr "Type a Char then press Enter to echo the Char:\n"
                 x <- getChar
                 putChar x
                 putStr "\n"

ex1b :: IO ()
ex1b = do putStr "Type a String then press Enter to echo the String: \CR"
                 y <- getLine
                 putStr y
                 putStr "\CR"
                 putStr ""

ex1c :: IO (Char, Char)
ex1c = do putStr "At each blinking cursor type a Char then press Enter to echo two Char:\n"
                getChar >>= \x ->
                    getChar >>= \_ ->
                        getChar >>= \y ->
                            return (x,y)       

GHCi:

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

Prelude>  ex1a
Type a Char then press Enter to echo the Char: 
a
a
Prelude>

Prelude>  ex1b
Type a String then press Enter to echo the String: 
Hello World!
Hello World!
Prelude>  

Prelude>  ex1c
At each blinking cursor type a Char then press Enter to echo two Char:
a
b
('a','b')
Prelude>

Prelude>  :type (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b  -- Takes something of IO a, and a function of (a to IO b), and returns IO b.
Prelude>

3.3.3.2. Example 2

GHCi:

Prelude>  let main = putStrLn "Hello, world!"
Prelude>

Prelude>  main
Hello, world!
Prelude>

3.3.3.3. Example 3

Module:

module ExThree where

main = do putStrLn "Type a line of text and then press Enter to echo the line of text: "
                 line <- getLine
                 print line

GHCi:

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

Prelude>  main
Type a line of text and then press Enter to echo the line of text: 
Hello, world!
"Hello, world!"
Prelude> 

3.3.3.4. Example 4

Module:

module ExFour where

-- GetChar :: IO Char
-- PutChar :: Char -> IO ()

-- Reading a string from the keyboard.

myGetLine :: IO [Char]
myGetLine = do x <- getChar
                           if x == '\n' then  -- '\n' is escape sequence for new line.
                              return []
                           else
                              do xs <- myGetLine
                                   return (x:xs)  

-- Writing a string to the screen:

myPutStr            :: String -> IO ()
myPutStr []        = return ()
myPutStr (x:xs) = do putChar x
                                   myPutStr xs
  
-- Writing a string and moving to a new line:

myPutStrLn      :: String -> IO ()
myPutStrLn xs = do myPutStr xs
                                 putChar '\n'
 
main  = do myPutStr "Enter a string then press Enter: "
                   xs <- myGetLine
                   myPutStr "The string has "
                   myPutStr (show (length xs))
                   myPutStrLn " characters counting punctuation and white-space."

GHCi:

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

Prelude>  main
Enter a string then press Enter: Hello, world!
The string has 13 characters counting punctuation and white-space.
Prelude>

4. CONCLUSION

There are many ways to write Haskell programs. The number of ways will change as time goes by because our needs as a society will change. Haskell must evolve to meet those needs or Haskell will be replaced by other languages. such as Python.

5. 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 UNWRAP WRAP INTRODUCTION

REVISED: Thursday, February 8, 2024

Haskell code shows copious amounts of (>>=) pronounced bind.

A Monad is a data structure which implements a Monad type class and satisfies Monad laws. A Monad typeclass defines two functions, the (>>=) and the return that know how to unwrap and wrap data. (>>=) bind is used to unwrap data and apply it to a function which takes the data as input and outputs a monad. (>>=) binds the unwrapped result of the computation on the left to the parameter of the one on the right. return is used to wrap data into a monad's type constructor.

Unwrap is the deconstructor in Haskell; destructing/unwrapping. Wrap is the constructor in Haskell; constructing/wrapping. You can also think of IO as a wrapper. The unwrapping of >>= cancels out the wrapping done by return, leaving only the function.

1. HASKELL WRAP UNWRAP EXAMPLE 1

The identity monad is a monad that does nothing special.

"Copy Paste" the following example into your text editor and "File Save As" WrapUnwrap.hs to your working directory.

module WrapUnwrap where

import Prelude hiding (Maybe(..))

import Control.Monad
import Control.Applicative

data Wrap a = Wrap a deriving Show

instance Functor Wrap where
   fmap f (Wrap a) = Wrap (f a)
   fmap _ Nothing  = Nothing

instance Monad Wrap where           
   return a = Wrap a
   Wrap a >>= f = f a   

instance Applicative Wrap where
   pure = Wrap
   Wrap f <*> Wrap a = Wrap (f a)
   _      <*> _      = Nothing

f :: Num a => a -> Wrap a
f a = Wrap (a + 1)                                -- Returns an incremented wrapped result.

(>>=) f (Wrap a) = f a                          -- unwrap does the exact opposite of wrap.

Load the example into GHCi.

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

As shown below we can take data and wrap it inside a data type and then increment it while it is wrapped in that data type:

Prelude>  f 2
Wrap 3
Prelude>

2. HASKELL UNWRAP WRAP EXAMPLE 2

Consider the following Functor:

class Functor f where
     fmap :: (a -> b) -> f a -> f b

instance Functor Maybe where
     fmap _ Nothing = Nothing
     fmap f (Just x)   = Just (f x)

If a value is wrapped in Just the fmap calls the function on the unwrapped value, and then rewraps it in Just.

3. HASKELL WRAP EXAMPLE 3

Wrap was easy to see in Example 1. You have to look closer to see wrap in Example 2.

"Copy Paste" the following example into your text editor and "File Save As" JustNothing.hs to your working directory.

module JustNothing where

import Prelude hiding (Maybe(..), lookup)

data Maybe a = Just a | Nothing
  deriving (Eq, Ord, Show)

pie :: [(String, String)]
pie = [("3.141592653589793", "pi")]

lookup key [] = Nothing
lookup key ((k, v) : rest) = if key == k then Just v else lookup key rest

main = do
  putStrLn "Please type pi to 15 decimal places then press Enter."
  word <- getLine  -- Notice getLine has type "getLine :: IO String",  <- is used to unwrap String from the IO action and bind it to word.
  print (lookup word pie)  -- Notice word has type "word :: String", not IO String; therefore, word is not an IO action. 
  if word == "3.141592653589793"
     then return ( "Congratulations!" )
     else main  

Load the example into GHCi:

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

Run the example in GHCi:

Prelude>  main
Please type pi to 15 decimal places then press Enter.
3.141592653589793
Just "pi"
"Congratulations!"
Prelude>

4. SUMMARY

The Haskell programming language is a functional language that makes heavy use of monads. A monad consists of a type constructor M and two operations, bind >>= and return. The return operation takes a value from a plain type and puts it into a monadic container using the constructor. The bind >>= operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline. This process effectively creates an action that chooses the next action based on the results of previous actions. Therefore, we should be able to determine our next action based on the results of previous actions. In other words, if x is a computation, and f is a function x >>= f is a computation which runs x, then applies f to its result, getting a computation which it then runs. Monads in Haskell can be thought of as composable computation descriptions.

5. CONCLUSION

Using return and bind we can wrap data and manipulate the wrapped data while keeping that data wrapped. We can also chain functions together that wrap. And in the process of doing these things we learn how monads work.

The unwrap wrap analogy is used to help you acquire intuition regarding how monads work. However, do not take unwrap wrap too literally. Unwrap wrap are mental tools to help you eventually gain the insight needed to think of monads in a computational context not in a unwrap wrap context.

6. 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 LOOKUP TABLE DICTIONARY

REVISED: Wednesday, January 24, 2024

1. HASKELL LOOKUP TABLE DICTIONARY

Shown below is a simple easy to understand Haskell lookup table dictionary program:

module Rhymes where

import Prelude hiding (Maybe(..), lookup)

{-
Representing failure using Maybe monad.
Using monads for error handling, also known as exception handling.
Data keyword introduces type Maybe a.
a is a place holder a generic variable.
Just and Nothing are constructors of type Maybe.
-}

data Maybe a = Just a | Nothing
deriving (Eq, Ord, Show)

{-
Lookup Table Dictionary.
A lookup table dictionary relates keys k to values v.
First tuple String is the key k.
Second tuple String is the value v.
-}

rhyme :: [(String, String)]
rhyme = [("fleece", "fleas")
           ,("snow", "go")
          ,("walk", "stalk")
          ,("jaws", "pause")
          ,("fair", "there")
          ,("there", "underwear")
          ,("nose", "toes")
  ,("nice", "lice")
  ,("toes", "blows")
          ,("lice", "ice")]

{-
Function for looking up keys k in Lookup Table Dictionary.
Found value v is returned wrapped in a Just.
You could unwrap Maybe with case statements.

rest is rest of Table.
-}

lookup key [] = Nothing   -- Empty String
lookup key ((k, v) : rest) = if key == k then Just v else lookup key rest

{-
No key match default value.
-}

fromMaybe def (Just a) = a
fromMaybe def Nothing = def

{-
getLine can be thought of as a monadic function of type () -> IO String a monadic action which reads a line of text from the terminal, returning the line of text read as a string. However, its type is IO String. 

putStrLn is a function which happens to be in the IO monad and takes a string as input and displays it on the terminal, also outputting a newline character at the end.
-}

main = do
  putStrLn "Type word to rhyme or type exit then press Enter."
  word <- getLine
  if word == "exit"
      then do 
             return ()
      else do  
              let poetry = lookup word rhyme
             print (fromMaybe "Not found! Update Poetry Lookup Table Dictionary!" poetry)
             main    

2. EXAMPLE PROGRAM OUTPUT

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

Prelude>  main
Type word to rhyme or type exit then press Enter.

fleece

"fleas"
Type word to rhyme or type exit then press Enter.

snow

"go"
Type word to rhyme or type exit then press Enter.

exit

Prelude>

3. EXAMPLE POEM

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

4. lookup AND Maybe a

As you know a lookup table dictionary is a table which relates keys to values. As shown above the lookup function and the Maybe a features work very well with a lookup table dictionary. I was very impressed with how easy it was to create and use a lookup table dictionary.

Please share with us your comments concerning your successful and unsuccessful lookup table dictionary experiences.

5. CONCLUSION

In this tutorial you have been introduced to the Haskell lookup table dictionary.

6. 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 EQUATIONAL REASONING

REVISED: Thursday, February 8, 2024

Haskell Equational Reasoning.

x + y = y + x                      -- Commutative Laws
x * y = y * x                

(x + y) + z = x + (y + z)     -- Associative Laws.
(x * y)  * z = x * (y * z) 

x * (y + z) = x * y + x * z  -- Distributive Laws.
(x + y) * z = x * z + y * z

I.  HASKELL EQUATIONAL REASONING EXAMPLES 

A. FUNCTION RECEIVES LIST RETURNS NUMBER

1. LIST LENGTH

"Copy, Paste" the following program into your text editor and "File, Save As" eqRes1.hs in your working directory.

eqRes1            :: [a] -> Int
eqRes1 []        = 0
eqRes1 (x:xs) = 1 + eqRes1 xs

Load the eqRes1 program into GHCi and call the function eqRes1 with the list [1,2,3]. 

GHCi, version 9.8.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude>

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

Prelude>  eqRes1 [1,2,3]
3
Prelude>

[1,2,3] is shorthand notation for 1 : (2 : (3 : [])).

Equational reasoning is replacing equals with equals; i.e., proving one expression is equal to another.

eqRes1 [1,2,3]  -- Total integers in list 1 + 1 + 1 + 0 = 3.
= 1 + eqRes1 [2,3]
= 1 + (1 + eqRes1 [3])
= 1 + (1 + (1 + eqRes1 []))
= 1 + (1 + (1 + 0))
= 3

2. LIST SUM

"Copy, Paste" the following program into your text editor and "File, Save As" eqRes2.hs in your working directory.

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

Load the eqRes2 program into GHCi and call the function eqRes2 with the list [1,2,3]. 

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

Prelude>  eqRes2 [1,2,3]
6
Prelude>

eqRes2 [1,2,3]  -- List sum 1 + 2 + 3 + 0 = 6. 
= 1 + eqRes2 [2,3]
= 1 + (2 + eqRes2 [3])
= 1 + (2 + (3 + eqRes2 []))
= 1 + (2 + (3 + 0))
= 6

B. FUNCTION RECEIVES TWO LISTS RETURNS ONE LIST

1. APPEND

"Copy, Paste" the following program into your text editor and "File, Save As" eqRes3.hs in your working directory.

import qualified Prelude as P

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

Load the eqRes3 program into GHCi and call the function (++) with the lists [1,2,3] [4,5,6].

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

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

[1,2,3] ++ [4,5,6]
= 1 : ([2,3] ++ [4,5,6])
= 1 : (2 : ([3] ++ [4,5,6]))
= 1 : (2 : (3 : ([] ++ [4,5,6])))
= 1 : (2 : (3 : [4,5,6]))
= 1 : (2 : [3,4,5,6])
= 1 : [2,3,4,5,6]
= [1,2,3,4,5,6] 

2. ZIP

"Copy, Paste" the following program into your text editor and "File, Save As" eqRes4.hs in your working directory.

import qualified Prelude as P

zip :: [a] -> [b] -> [(a,b)]
zip [] ys = []
zip xs [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

Load the eqRes4 program into GHCi and call the function zip with the lists [1,2,3] [4,5,6,7].

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

Prelude>  zip [1,2,3] [4,5,6,7] 
[(1,4),(2,5),(3,6)]
Prelude> 

zip [1,2,3] [4,5,6,7]  -- Notice, lists are of different lengths.
= (1,4) : zip [2,3] [5,6,7]
= (1,4) : ((2,5) : zip [3] [6,7])
= (1,4) : ((2,5) : ((3,6) : zip [] [7]))  -- zip stops at first empty list.
= (1,4) : ((2,5) : ((3,6) : []))
= (1,4) : ((2,5) : [(3,6)])
= (1,4) : [(2,5), (3,6)]
= [(1,4), (2,5), (3,6)]  -- Output list length is shortest input list.

II. CONCLUSION

In this tutorial you have been introduced to Haskell Equational Reasoning.

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.

HASKELL FOLDL INTRODUCTION

REVISED: Friday, October 25, 2024

I. FOLDL 

foldl saves a lot of code. We could do a "Copy Paste" of the following two functions and then do a "File, Save As" facProd.hs to our working directory.

myProduct :: (Num a) => [a] -> a
myProduct = foldl (*) 1

myFactorial :: Int -> Int
myFactorial n = myProduct [1..n]

GHCi, version 9.8.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude>

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

And then call the myFactorial function which in turn calls the myProduct function.

myFactorial :: Int -> Int

Prelude>  myFactorial 3
6
Prelude>

Or we can just call the myProduct function and obtain the factorial.

myProduct :: (Num a) => [a] -> a

Prelude>  myProduct [1,2,3]
6
Prelude> 

With a little upfront thinking we could have written myProduct as myFactorial.

myFactorial :: (Num a) => [a] -> a
myFactorial = foldl (*) 1

However, notice what happened. Looking closely at both function signatures if we wanted the factorial using both of our original functions we only have to enter the function name and the one integer we want the factorial of.

myFactorial 3

Now we have to enter the function name and a list of all the integers that are part of the factorial sequence.

myProduct [1,2,3]

Our first choice using two functions was really the best choice. However, the point I am trying to make is, often foldl is used and we do not even know it is being used. It can be a behind the scenes player that does a lot of work for us.

Based on comments from the tutorial audience, use foldl' from the Data.List. It apparently does the same thing as the Prelude foldl; however, it appears to be more efficient. Use foldr on lists that might be infinite or where the fold is building up a data structure. Use foldl' if the list is known to be finite and comes down to a single value.

II. CONCLUSION

In this tutorial you have been introduced to the advantages of using Haskell foldl.

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.

IS ⊥ BOTTOM THE HASKELL RED-HEADED STEPCHILD?

REVISED: Thursday, February 8, 2024

Haskell And Bottom.

I. IS ⊥ BOTTOM THE HASKELL RED-HEADED STEPCHILD?

Undefined or bottom written with an up tack or falsum ⊥ refers to a computation which never completes successfully. Think of bottom as representing a computation which will not halt, it does not terminate. The glyph of the up tack appears as an upside down tee symbol, and is sometimes called eet, the word tee in reverse. Bottom or whatever you prefer to call it represents a computation which causes our program to fail. However, the ⊥ bottom type is a sub-type of all types! For example, the type Bool does not just include True, False it really includes True, ⊥, False. The type () with only one element actually has two: ⊥, (). The type Integer really includes [⊥, 0, 1, 2, 3..]. The same inclusion can be said of all types. Adding ⊥ to a set of values is called lifting. All normal Haskell types are lifted.

Why do we rarely see discussions devoted to bottom? Maybe it is related to our technological evolution. In the past we appeared to need information on large objects we could see with the unaided eye, we did not seem as interested in the very small, the bottom. Our technology has evolved, now we need information on both the very large and the very small. We need to rethink the importance of bottom. Granted Haskell does not have sub-types; however, bottom should be thought of as more than just not terminating or an error message. Seeing a bottom should spark our creative thought processes. There is more to a bottom than meets our unaided eye.

One area of creative thought processes is the math field of calculus which calculates limits and derivatives. How often have you recently seen Haskell used to solve non lambda calculus, calculus problems? These of course are problems calculating numbers approaching infinity or zero. What is infinity, is infinity bottom? What is zero? We need Haskell to help us with the creative what is ... problem types. Haskell is based on math; however, I have seldom seen easy to understand, Haskell non lambda calculus, calculus limits or derivative functions outside of Haskell Cabal. We have a lot of work ahead of us. 

I love Haskell, it is my favorite programming language; however, is the ⊥ bottom type the Haskell red-headed stepchild?

II. CONCLUSION

In this tutorial, you have been introduced to Haskell ⊥ bottom.

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.

HASKELL SIEVE OF ERATOSTHENES

REVISED: Thursday, February 8, 2024

Haskell And Prime Numbers.

I. SIEVE OF ERATOSTHENES

Eratosthenes of  Cyrene (275-194 B.C.) was a Greek mathematician who created the Sieve of Eratosthenes, an algorithm for rapidly locating all prime numbers within a range of integers.

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

sieve :: Integral a => [a] -> [a]
sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

primes :: [Integer]
primes = sieve [2..]

main = print $ take 100 primes

Load the example into GHCi as follows:

GHCi, version 9.8.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude>

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

Call the main function, take the first 100 prime numbers generated by our program, and print them as follows:

Prelude>  main
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173, 179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263, 269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359, 367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457, 461,463,467,479,487,491,499,503,509,521,523,541]
Prelude>

II. PRIME NUMBER DEFINITION

A prime number is a natural number, a counting number, greater than 1 with no positive divisors or factors other than 1 and itself.

III. PRIMES

primes is a function name, primes is not a Haskell keyword.

primes :: [Integer]
primes = sieve [2..]

The initial prime generated by sieve is 2. 

IV. LIST COMPREHENSION

The following sieve function is a list comprehension which takes, as shown in its type signature, a list as its input and produces a list as its output.

sieve :: Integral a => [a] -> [a]
sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

The sieve function obtains its arguments (p : xs) by deconstructing the beginning of the list sieve, to get its head p and tail xs.

After we have the arguments, read the sieve function from right to left.

The list comprehension iterates over xs, binding each element to x, which it returns if x is not (/=) evenly divisible by p.

, comma before the predicate is pronounced, "such that".

<- arrow is pronounced, "drawn from". A generator expression binds a variable on the left of a <- arrow to an element of the list on the right.

| pipe is pronounced, "such that". The part before the | pipe, x, is called the output function. The expression on the left of the | pipe is evaluated for each combination of generator expressions on the right.

p : sieve puts p on the front of a new list, which is constructed by calling sieve.

The sieve function determines whether or not the head of the list is a prime, and then calls itself recursively on the tail of the list. Therefore, sieve is a tail recursive function.

sieve is a function name, sieve is not a Haskell keyword.

The function sieve is defined in terms of itself; therefore, sieve is recursive. Haskell is lazily evaluated, and it will do no more work than is necessary, and stop once the take 100 primes have been calculated.

As shown below [2..] could produce an infinite number of integers starting from the number 2 if it were allowed to do so. When it is run as part of the total program we are saved from the imperative programming results of an infinite loop by the lazy nature of Haskell's functional programming language in which elements of the range object are only generated when they are needed.

Prelude>  [2..]
[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25, ...

The sieve function takes a single list of integers as its argument, and assumes that the first integer in the list is a prime. The sieve function then removes from the list integers that are not prime.

V. TAKE

take is a Haskell Prelude function name.

The Prelude take function returns a sublist consisting of the first k elements from the sublist. Therefore, we are working with several lists, the [2..] list of integers, the take sublist of prime numbers, and each new list created from the integers which could not be divided by the last prime division.

VI. ANALYSIS

When our Sieve of Eratosthenes starts [2..] provides us with the prime number, 2 and a list of xs.

p is bound to 2.

x is bound to 2.

In other words:

First, sieve is passed a list of all integers greater than or equal to 2.

Second, sieve uses 2 as the first prime and passes itself a list of all remaining integers not divisible by 2 ([3, 5, 7, 9, 11, 13, ...]).

Third, sieve uses the 3 as the second prime and passes itself a list of all remaining integers not divisible by 3 ([5, 7, 11, 13, ...]).

Fourth, this process proceeds recursively until the number of primes necessary to satisfy the take requirement of 100 prime numbers is met.

The lists discussed above are list generators, functions which calculate only on demand the next number in a list.

VII. CONCLUSION

In this tutorial, you have been introduced to using Haskell to find prime numbers.

VIII. 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.