HASKELL FOLDL INTRODUCTION

REVISED: Saturday, February 10, 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.