HASKELL TRIANGULAR NUMBER SEQUENCE

REVISED: Monday, September 23, 2024

1. INTRODUCTION

An equilateral triangle is a triangle with all three sides of equal length and all angles equal to 60°.

Triangular numbers
t n = (n * (n+1)) `div` 2
are the number of objects needed to form an equilateral triangle.

This tutorial shows a method for using Haskell to compute the Triangular Number Sequence of objects needed to form equilateral triangles:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431...

2. HASKELL PROGRAM

A Haskell program used to compute the Triangular Number Sequence is as follows:

-- C:\Users\Tinnel\Haskell2024\triangularNS.hs

import Data.List
import System.IO

main :: IO ()  -- Has type I/O action.
main = do {  putStrLn ""  -- putStrLn Has type I/O action.
           ; putStrLn "=========================================================="
           ; putStrLn ""
           ; putStrLn "TRIANGULAR NUMBER SEQUENCE"
           ; putStrLn ""
           ; putStrLn "h = 1      2       3         4          5"
           ; putStrLn "      **     ***     ****     *****     ******"
           ; putStrLn "              ***   h****     *****     ******"
           ; putStrLn "                       ****     *****     ******"
           ; putStrLn "                       h+1     *****     ******"
           ; putStrLn "                                              ******"
           ; putStrLn ""
           ; putStrLn "The above rectangles are h high and h + 1 wide  and contain 2 equilateral triangles."
           ; putStrLn ""
           ; putStrLn "t h is the total stars in one equilateral triangle."
           ; putStrLn "t h = h * (h + 1) `div` 2"
           ; putStrLn ""
           ; putStrLn "For example"
           ; putStrLn "t 5 = 5 * (5 + 1) `div` 2"
           ; putStrLn "equals 15 stars in one equilateral triangle 5 stars high."
           ; putStrLn ""
           ; putStrLn "=========================================================="
           ; putStrLn ""
           ; putStrLn "Type a positive integer representing an equilateral triangle with a height of h then press Enter."
           ; s <- getLine -- getLine is a function, getLine :: IO String
           ; putStrLn ""
           ; putStrLn "=========================================================="
           ; putStrLn ""
           ; let h = (read s)::Integer
           ; putStrLn "The Triangular Number is:"
           ; putStrLn ""
           ; let z = fromIntegral(t h)
           ; print z
           ; putStrLn ""
           ; putStrLn "=========================================================="
           ; putStrLn ""
          }
--
-- Haskell has different functions for integer and 'fractional' division.
-- Int is not an instance of Fractional so you can't use (/) with Int.
-- t :: Fractional a => a -> a

t :: Integral a => a -> a
t h = h * (h + 1 )`div` 2

3. GHCi RUN

*Main> :l triangularNS
[1 of 1] Compiling Main             ( triangularNS.hs, interpreted )
Ok, modules loaded: Main.
*Main> main

=========================================================================

TRIANGULAR NUMBER SEQUENCE

h = 1      2       3        4          5
      **     ***     ****     *****     ******
              ***   h****     *****     ******
                       ****     *****     ******
                       h+1    *****     ******
                                             ******
The above rectangles are h high and h + 1 wide and contain 2 equilateral triangles.

t h is the total stars in one equilateral triangle.
t h = h * (h + 1) `div` 2

For example
t 5 = 5 * (5 + 1) `div` 2
equals 15 stars in one equilateral triangle 5 stars high.

=========================================================================

Type a positive integer representing an equilateral triangle with a height of h then press Enter.
5

=========================================================================

The Triangular Number is:
15

=========================================================================

*Main>

4. CONCLUSION

In this tutorial you have seen a basic approach for using Haskell to compute the Triangular Number Sequence.

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 TEST FOR PRIME NUMBER

REVISED: Monday, September 23, 2024

1. INTRODUCTION

The search is on for larger and larger prime numbers. This tutorial will show a method for testing large positive integers to see if they are prime numbers.

The largest explicitly known prime keeps growing. For example,  (2^32582657 - 1),  (2^43112609 - 1) and (2^74207281 - 1)  were recently discovered very large prime numbers. Methods for quickly testing to see if very large positive integers are prime numbers are important tools used in the search for larger prime numbers.

2. HASKELL PROGRAM

The Haskell program we will use in this tutorial to test a positive integer for prime is as follows:

-- C:\Users\Tinnel\Haskell2024\test.hs

import Data.List
import System.IO

main :: IO ()  -- Has type I/O action.
main = do {  putStrLn ""  -- putStrLn Has type I/O action.
           ; putStrLn "=========================================================="
           ; putStrLn ""
           ; putStrLn "Type a positive integer you want to test for prime then press Enter."
           ; s <- getLine -- getLine is a function, getLine :: IO String
           ; let n = (read s)::Integer
           ; putStrLn ""
           ; putStrLn "=========================================================="
           ; putStrLn ""
           ; let test = if (p n == 0 || m n == 0) && n /= 1
                        then "True"
                        else if (n == 2 || n == 3)
                             then "True"
                             else if (n == 0 || n == 1)
                                  then "False"
                                  else "False"
           ; putStrLn "QUESTION: True or False, is the number you entered a prime number?"
           ; putStrLn ""
           ; putStrLn ("ANSWER: " ++ test ++ ".")
           ; putStrLn ""
           ; putStrLn "=========================================================="
           ; putStrLn ""
          }

-- Adds 1 and divides by 6; a remainder means False.
p :: Integral a => a -> a
p n = (n + 1) `mod` 6

-- Subtracts 1 and divides by 6; a remainder means False.
m :: Integral a => a -> a
m n = (n - 1) `mod` 6

3. GHCi RUN

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

*Main> main

=========================================================================

Type a positive integer you want to test for prime then press Enter.
29996224275833

=========================================================================

QUESTION: True or False, is the number you entered a prime number?

ANSWER: True.

=========================================================================

*Main>

4. CONCLUSION

The above Haskell program is a quick way to determine if very large positive integers are prime numbers.

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 PROOF BY CONTRADICTION EXAMPLE 1

REVISED: Saturday, October 5, 2024

1. INTRODUCTION

1.1 GIVEN

1.1.1 Consider the following proposition:

For all n in the set of positive Natural numbers, the function f n = n ^ 2 + n + 41 is a prime number is True.

1.1.2 Definition

A Prime Number is a whole number greater than or equal to 2 which has two and only two factors; for example, it can be divided without a remainder only by 1 and itself.

2. HASKELL PROGRAM

2.1 TO BE PROVED

We will use a proof by contradiction.

Therefore, we assume that the statement of the proposition that for all n in the set of positive Natural numbers, the function f n = n ^ 2 + n + 41 is a prime number is False.

2.2 PROOF

The Haskell program used for the proof is as follows:

-- C:\Users\Tinnel\Haskell2024\proof1.hs

import Data.Char
import Data.List
import Data.List (elemIndex)
import Data.Map
import Data.Maybe
import Data.Set
import System.IO
--
--
main :: IO ()    -- Has type I/O action.
main = do {  putStrLn ""    -- putStrLn Has type I/O action.
                   ; putStrLn "======================================================"
                   ; putStrLn ""
                   ; putStrLn "Prove the proposition that for all n in the set of positive Natural numbers, the function"
                   ; putStrLn ""
                   ; putStrLn "f n = n ^ 2 + n + 41"
                   ; putStrLn ""
                   ; putStrLn "is a prime number is False."
                   ; putStrLn ""
                   ; putStrLn "======================================================"
                   ; putStrLn ""
                   ; putStrLn "Type a positive integer value for n then press Enter."
                   ; s <- getLine -- getLine is a function, getLine :: IO String
                   ; putStrLn ""
                   ; putStrLn "======================================================"
                   ; putStrLn ""
                   ; putStrLn ("Computing the function with n equal to " ++ s ++ ".")
                   ; putStrLn ""
                   ; let n = (read s)::Integer  -- Type converted from IO String s to Integer n.
                   ; let z = f n  -- z is the integer prime number computed by n.
                   ; let zS = show z  -- Type converted from Integer z to String z.
                   ; putStrLn ("f n = n ^ 2 + n + 41 equals " ++ zS ++ ".")
                   ; putStrLn ""
                   ; putStrLn "======================================================"
                   ; putStrLn ""
                   ; putStrLn "The list of the first 300 prime numbers starting with 2 is as follows:"
                   ; putStrLn ""
                   ; print p  -- The list of prime numbers.
                   ; putStrLn ""
                   ; putStrLn "======================================================"
                   ; putStrLn ""
                   ; putStrLn ("QUESTION: True or False is " ++ zS ++ " a prime number?")
                   ; putStrLn ""
                   ; let i = if elem z p == True then "True" else "False"
                   ; putStrLn ("ANSWER: " ++ i ++ ".")
                   ; putStrLn ""
                   ; putStrLn ""
                   ; putStrLn ""
                 }
--
--
-- t computes prime numbers.
t :: Integral a => [a] -> [a]
t (p : xs) = p : t [x | x <- xs, x `mod` p /= 0]

-- primes is a list of prime numbers computed by t.
primes :: [Integer]
primes = t [2..]  -- Starting with 2 because zero and 1 are not prime numbers.
                         -- However, main can compute n = 0, and n = 1.

-- p is a list of prime numbers taken from those computed by t.
p :: [Integer]
p = take 300 primes

-- f n computes each number compared to the list p for prime.
f :: Num a => a -> a
f n = n ^ 2 + n + 41

-- read :: Read a => String -> a
-- (==) :: (Eq a) => a -> a -> Bool

3. GHCi RUN

GHCi, version 9.8.1: http://www.haskell.org/ghc/  :? for help
Prelude> :l proof1
[1 of 1] Compiling Main             ( proof1.hs, interpreted )
Ok, modules loaded: Main.

*Main> main

=========================================================================

Prove the proposition that for all n in the set of positive Natural numbers, the function

f n = n ^ 2 + n + 41

is a prime number is False.

=========================================================================

Type a positive integer value for n then press Enter.
5

=========================================================================

Computing the function with n equal to 5.

f n = n ^ 2 + n + 41 equals 71.

=========================================================================

The list of the first 300 prime numbers starting with 2 is as follows:

[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,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987]

=========================================================================

QUESTION: True or False is 71 a prime number?

ANSWER: True.

4. TRUTH TABLE

Running the Haskell program for each element of n we obtain the truth table shown below:

n    f n = n^2 + n + 41      Prime
---- ------------------------     -------
  0                           41    True
  1                           43    True
  2                           47    True
  3                           53    True
  4                           61    True
  5                           71    True
  6                           83    True
  7                           97    True
  8                         113    True
  9                         131    True
10                         151    True
11                         173    True
12                         197    True
13                         223    True
14                         251    True
15                         281    True
16                         313    True
17                         347    True
18                         383    True
19                         421    True
20                         461    True
21                         503    True
22                         547    True
23                         593    True
24                         641    True
25                         691    True
26                         743    True
27                         797    True
28                         853    True
29                         911    True
30                         971    True
31                       1033    True
32                       1097    True
33                       1163    True
34                       1231    True
35                       1301    True
36                       1373    True
37                       1447    True
38                       1523    True
39                       1601    True
40                       1681    False  Q.E.D.
41                       1763    False
42                       1847    True
43                       1933    True
44                       2021     Outside of the first 300 prime number range.

5. CONCLUSION

The proposition that for all n in the set of positive Natural numbers, the function f n = n ^ 2 + n + 41 is a prime number is False.

As shown above, you must be careful when concluding whether a proof is True or False. The first 39 tests would lead most people to assume f n = n^2 + n + 41 could be used to compute prime numbers. However tests 40 and 41 show the proposition is not True, it is False.

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 PARSING FILE RECORDS EXAMPLE

REVISED: Thursday, October 10, 2024

1. INTRODUCTION

Using Haskell to parse records stored on a file is a good way to begin learning Haskell data structures.

2. HASKELL PARSING FILE RECORDS EXAMPLE

This example parses the records in the annual customer sales file sales1945.txt to obtain the total sales for one customer.  You can create the sales1945.txt file from the Annual Sales File Listing printed by the module. Each record in the file has a field for custID (customer identification), invoice (invoice number), usdLines (United States Dollars), and mmddyyyy (invoice date). The example computes the total annual sales to one customer based on the custID.

2.1 Module

{-

customerFilter  -- Function which creates a new list containing all records matching the customer ID.

customerID  -- The variable name for identification of the customer.

customerSales  -- Function which computes the customer total annual sales.

customerSalesFileRecords  -- The variable name containing all of the records for the entire annual sales file.

salesByCustomer  -- Function for user to input sales file name and customer ID.

sales  -- Function which creates a new list of only customer sales amounts.  

total  -- Function which turns each customer sales invoice amount String into a Double and totals the amounts. 

totalCustomerSales  -- The variable name for the total annual customer sales for one customer.

usdLines  -- Function which creates a new list of usdLines.

-}

module Sales where
import Data.List.Split(endBy)
import Data.List(isInfixOf, isPrefixOf)

{-

The function aims to compute total annual USD sales for one customer ID.

The '.' operator is used to compose functions. Function composition is a way to "compose" two functions into a single function.

map takes a function and a list and applies that function to every element in the list, producing a new list.

filter is a function that takes a predicate and a list and then returns the list of elements that satisfy the predicate.

A predicate is a function that tells whether something is true or not.

lines function is defined in the Data.List library. lines takes a String, and breaks it up into a list of strings, splitting on newlines.

dropWhile creates a list from another list taking from it its elements from when the condition fails for the first time till the end of the list.

isInfixOf function takes two lists and returns True iff the first list is contained, wholly and intact, anywhere within the second.

isPrefixOf function takes two lists and returns True iff the first list is a prefix of the second.

endBy creates a new list by splitting a String into chunks terminated by the given subsequence which is "@" in the example below.
 

-}

customerSales :: String -> String -> Double
customerSales customerSalesFileRecords customerID  = total.sales.usdLines $ customerFilter customerSalesFileRecords customerID
                                    where usdLines = map $ filter (isPrefixOf "usd").lines
                                               sales       = map (dropWhile (> ' ')).concat
                                               total        = sum.map (\x -> read x :: Double)
                                               customerFilter customerSalesFileRecords customerID = filter (isInfixOf customerID) $ endBy "@" customerSalesFileRecords

{-

Function purpose is for user to input sales file name and customer ID.

Function prints sales file records.

Function returns total annual USD sales for one customer ID

  

-}

                                    
salesByCustomer :: IO Double
salesByCustomer = do
    putStrLn "Enter Annual Sales File Name:" 

    -- For example, enter sales1945.txt
    customerSalesFileRecords <- getLine >>= readFile

    -- Reads in entire sales1945.txt file
    putStrLn "\nAnnual Sales File Listing:\n"
    putStrLn customerSalesFileRecords                                 
    putStrLn "\nEnd Of Annual Sales File Listing:\n"
    putStrLn "Enter Customer ID:"

    -- For example, a1a
    customerID <- getLine
    return $ customerSales customerSalesFileRecords customerID
    
main :: IO()
main = do
    totalCustomerSales <- salesByCustomer
    putStrLn ("\nCustomer Total USD Sales: " ++ show totalCustomerSales)

2.2 GHCi

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 Sales
[1 of 1] Compiling Sales              (Sales.hs, interpreted )
Ok, modules loaded: Sales.
(0.09 secs, 34185296 bytes)
Prelude>

Prelude>  main
Loading package split-0.2.2 ... linking ... done.
Enter Annual Sales File Name:
sales1945.txt

Annual Sales File Listing:

custID a1a
invoice i1
usd 1.01
mmddyyyy 0101i945
@
custID b2b
invoice i2
usd 5678.05
mmddyyyy 02021945
@
custID c3c
invoice i3
usd 910.12
mmddyyyy 03101945
@
custID d4d
invoice i4
usd 1234.11
mmddyyyy 04111945
@
custID d4d
invoice i5
usd 5678.06
mmddyyyy 05211945
@
custID c3c
invoice i6
usd 910.01
mmddyyyy 06081945
@
custID b2b
invoice i7
usd 1111.08
mmddyyyy 11121945
@
custID a1a
invoice i8
usd 1000.03
mmddyyyy 11131945
@
custID a1a
invoice i9
usd 100.01
mmddyyyy 12251945
@
custID a1a
invoice i10
usd 10.02
mmddyyyy 12251945
@

End Of Annual Sales File Listing:

Enter Customer ID:
a1a

Customer Total USD Sales: 1111.07
Prelude>

3. CONCLUSION

In this tutorial, you have seen a basic approach for using Haskell to parse file records.

4. 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 RECURSIVE DATA STRUCTURE TREE EXAMPLES

REVISED: Wednesday, October 9, 2024

1. INTRODUCTION

To learn how to code a recursive data structure tree start with the following three basic definitions: 

-- Firstly, the basic definition of a Tree.
data Tree a = Leaf a | Branch (Tree a) (Tree a)
   deriving (Eq, Show)

A Tree a is either a leaf, containing a value of type a or a branch, from which hangs two other trees of type Tree a.

-- Secondly, the basic definition of map for lists.
map              :: (a -> b) -> [a] -> [b]
map       _ [] = []
map f (x:xs) = f x : map f xs

-- Thirdly, the basic definition of foldr for lists.
foldr                 :: (a -> b -> b) -> b -> [a] -> b
foldr       f z []  = z
foldr f z (x:xs) = f x (foldr f z xs)

2. RECURSIVE DATA STRUCTURE TREE EXAMPLE 1

For details regarding this Example 1 code please refer to the following link.

Module 1:

module RDST1 where

import Prelude hiding (map, foldr)

data Tree a = Leaf a | Branch (Tree a) (Tree a)
   deriving (Eq, Show)

-- The basic map definition for a list is used to write the basic map definition for a tree. 
treeMap                       :: (a -> b) -> Tree a -> Tree b
treeMap                    f  = g where
   g                 (Leaf x) = Leaf (f x)
   g (Branch left right) = Branch (g left) (g right)

-- The basic foldr definition for a list is used to write the basic fold definition for a tree. 
treeFold                      :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeFold fbranch fleaf = g where g (Leaf x) = fleaf x
                                       g (Branch left right) = fbranch (g left) (g right)
 
tree1 :: Tree Integer
tree1 = Branch (Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Branch (Leaf 4) (Branch (Leaf 5) (Leaf 6)))) (Branch (Branch (Leaf 7) (Leaf 8)) (Leaf 9))

tree2 :: Tree Integer
tree2 = Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))

-- Doubles each value in tree.
doubleTree = treeMap (*2)

-- Sum of the Leaf values in tree.
sumTree = treeFold (+) id 

-- List of the Leaves of a tree.
fringeTree = treeFold (++) (: [])

main = do
    putStrLn $ "Original tree1: " ++ (show tree1)
    putStrLn $ "Original tree2: " ++ (show tree2)

GHCi:

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

Prelude>  main
Original tree1: Branch (Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Branch (Leaf 4) (Branch (Leaf 5) (Leaf 6)))) (Branch (Branch (Leaf 7) (Leaf 8)) (Leaf 9))
Original tree2: Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))
Prelude>

Prelude>  sumTree tree1
45
Prelude>

Prelude>  doubleTree tree1 
Branch (Branch (Branch (Leaf 2) (Branch (Leaf 4) (Leaf 6))) (Branch (Leaf 8) (Branch (Leaf 10) (Leaf 12)))) (Branch (Branch (Leaf 14) (Leaf 16)) (Leaf 18))
Prelude>

Prelude>  fringeTree tree1
[1,2,3,4,5,6,7,8,9]
Prelude>

Prelude>  fringeTree tree2
[1,2,3,4]
Prelude>

Prelude>  let tree3 = doubleTree tree1
Prelude>

Prelude>  tree3
Branch (Branch (Branch (Leaf 2) (Branch (Leaf 4) (Leaf 6))) (Branch (Leaf 8) (Branch (Leaf 10) (Leaf 12)))) (Branch (Branch (Leaf 14) (Leaf 16)) (Leaf 18))
Prelude>

Prelude>  fringeTree tree3
[2,4,6,8,10,12,14,16,18]
Prelude>

3. RECURSIVE DATA STRUCTURE TREE EXAMPLE 2

For details regarding this Example 2 code please refer to the following link.

Module 2:

module RDST2 where

data MyTree a = MyEmptyNode
              | MyFilledNode a (MyTree a) (MyTree a)
              deriving (Eq,Ord,Show,Read)

main :: IO ()
main  =
   do
      putStrLn "Begin program"

      let aMyTree = MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
      print aMyTree
      print (sumMyTree aMyTree)

      let bMyTree = MyFilledNode "r" (MyFilledNode "s" MyEmptyNode MyEmptyNode) (MyFilledNode "a" MyEmptyNode MyEmptyNode)
      print bMyTree

      putStrLn "End program"

sumMyTree                                       :: Num a => MyTree a -> a
sumMyTree MyEmptyNode             = 0
sumMyTree (MyFilledNode n t1 t2) = n + sumMyTree t1 + sumMyTree t2

GHCi:

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

Prelude>  main
Begin program
MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
10
MyFilledNode "r" (MyFilledNode "s" MyEmptyNode MyEmptyNode) (MyFilledNode "a" MyEmptyNode MyEmptyNode)
End program
Prelude>

4. RECURSIVE DATA STRUCTURE TREE EXAMPLE 3

For details regarding this Example 3 code please refer to the following link.

Module 3:

module RDST3 where

import Control.Applicative

data MyTree a = MyNode a [MyTree a]
                deriving (Show)

instance Functor MyTree where
   fmap f (MyNode x treeList) = MyNode (f x) (map (fmap f) treeList)

instance Applicative MyTree where
   pure x = MyNode x []
   (MyNode f treeFunctionList) <*> (MyNode x treeElementList) =
      MyNode (f x) ( (map (fmap f) treeElementList) ++ (map (<*> (MyNode x treeElementList)) treeFunctionList) )

instance Monad MyTree where
   return x = MyNode x []
   MyNode x treeList >>= f = MyNode x' (treeList' ++ map (>>= f) treeList)
      where MyNode x' treeList' = f x

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that MyTree behaves as a type constructor."

      let tree1 = MyNode 5 [MyNode 3 [], MyNode 2 []]
      print tree1

      let tree2 = MyNode "ABC" [MyNode "DEFG" [], MyNode "HIJKL" []]
      print tree2

      putStrLn "Tests that prove that MyTree behaves as a Functor."

      print (fmap (*2) tree1)
      print (fmap length tree2)

      putStrLn "Tests that prove that MyTree behaves as an Applicative."

      print ((MyNode (*2) []) <*> tree1)
      print ((MyNode (*2) [MyNode (+100) [], MyNode (+1000) []]) <*> tree1)
      print ((MyNode init []) <*> tree2)
      print ((MyNode init [MyNode reverse [MyNode tail []]]) <*> tree2)

      putStrLn "Tests that prove that MyTree behaves as a Monad."

      print (tree1 >>= (\x -> MyNode (x+200) []))
      print (tree2 >>= (\x -> MyNode (tail x) []))

      putStrLn "Program ends."

GHCi:

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

Prelude>  main
Program begins.
Tests that prove that MyTree behaves as a type constructor.
MyNode 5 [MyNode 3 [],MyNode 2 []]
MyNode "ABC" [MyNode "DEFG" [],MyNode "HIJKL" []]
Tests that prove that MyTree behaves as a Functor.
MyNode 10 [MyNode 6 [],MyNode 4 []]
MyNode 3 [MyNode 4 [],MyNode 5 []]
Tests that prove that MyTree behaves as an Applicative.
MyNode 10 [MyNode 6 [],MyNode 4 []]
MyNode 10 [MyNode 6 [],MyNode 4 [],MyNode 105 [MyNode 103 [],MyNode 102 []],MyNode 1005 [MyNode 1003 [],MyNode 1002 []]]
MyNode "AB" [MyNode "DEF" [],MyNode "HIJK" []]
MyNode "AB" [MyNode "DEF" [],MyNode "HIJK" [],MyNode "CBA" [MyNode "GFED" [],MyNode "LKJIH" [],MyNode "BC" [MyNode "EFG" [],MyNode "IJKL" []]]]
Tests that prove that MyTree behaves as a Monad.
MyNode 205 [MyNode 203 [],MyNode 202 []]
MyNode "BC" [MyNode "EFG" [],MyNode "IJKL" []]
Program ends.
Prelude> 

5. CONCLUSION

The purpose of this tutorial is not to discuss the code but to point out you should always start with the basic things you know about Haskell in order to understand the things you think are difficult. Learn the basic concepts they are the building blocks for understanding Haskell.

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 HIGHER ORDER FUNCTIONS

REVISED: Tuesday, October 15, 2024

1. INTRODUCTION

A function is called higher order if it takes a function as an argument or returns a function as a result. In Haskell, we refer to functions that take other functions as arguments and return new functions as combinators.

Higher order functions taking functions as arguments include map and filter.

The term curried is normally used for higher order functions that take their arguments one at a time and return a function as a result.

Haskell higher order functions can be used to define Embedded Domain Specific Languages (EDSLs).

2. MAP

map applies a function to every element of a list.

2.1. MAP DEFINED USING LIST COMPREHENSION

Defining a map using list comprehension makes it easy to see how a map applies a function f x to every element of a list of xs:

-- Functions passed to other functions are written with their type declarations surrounded by parentheses; i.e., (a -> b).
-- 1st argument is a function that takes an "a" and returns a "b".
map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]

2.2. MAP DEFINED USING RECURSION

Haskell programmers never use loops. Instead they either use recursion to do looping, or they use functions like map that take other functions as arguments.

Defining map using recursion:

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

3. FILTER

filter selects every element from a list that satisfies a condition or predicate.

3.1. FILTER DEFINED USING LIST COMPREHENSION

Given:
p x is a condition or predicate function.
xs is a list of xs.
x is an element drawn from the list of xs.
<- is pronounced "drawn from."
| pipe is pronounced "such that."
, comma before the condition or predicate is pronounced "such that."

filter defined using list comprehension:

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs , p x]

3.2. FILTER DEFINED USING RECURSION

filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs)
    | px            = x : filter p xs
    | otherwise = filter p xs

4. CURRIED

Functions with multiple arguments are defined in Haskell by currying. Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed.

In Haskell, all functions are considered curried. All functions in Haskell take just single arguments.

Curried functions can be partially applied. Partial application in Haskell involves passing less than the full number of arguments to a function that takes multiple arguments.

5. EMBEDDED DOMAIN SPECIFIC LANGUAGES (EDSLs)

Higher-order functions can be used in Haskell to define EDSLs which can be used to do many things including processing lists and building parsers. A Haskell EDSL is a language embedded inside of Haskell. An EDSL uses the library of functions provided by Haskell, often called combinators, because they combine their arguments into terms inside the EDSL. In essence, EDSLs are just Haskell libraries.

6. USER DEFINED

User-defined higher-order functions often use partial application. Partial application in Haskell involves passing less than the full number of arguments to a function that takes multiple arguments. This results in a new function taking the remaining number of parameters.

6.1. RECEIVE A FUNCTION

The function area is missing the value for the radius r. The radius function computes the area of the circle using a hard-coded value of 5 for the radius r. This is done by the function radius argument func receiving the function area with argument 5 as shown below.

-- C:\Users\Tinnel\areaCircle.hs

import Data.List
import System.IO

-- Area of Circle
area :: Floating a => a -> a
area r = pi * r ^ 2  -- The function area is missing the value for the radius r.

radius :: Num a => (a -> t) -> t  -- func receives area function (a -> t).
radius func = func 5 -- radius argument 5, the constant t, is passed into the function area.

areaCircle :: Double
areaCircle = radius area  -- areaCircle stores results of function radius with r of 5.

Prelude> areaCircle
78.53981633974483
Prelude> 

6.2. RETURN A FUNCTION

-- C:\Users\Tinnel\onePlus9.hs

import Data.List
import System.IO

addFunc :: Num a => a -> a -> a  -- When you type :t addFunc
addFunc x y = x + y

{-

The -> kleisli arrow operator is right-associative, and the function application is left-associative, meaning the type signature of addFunc actually looks like this:

addFunc :: Num a => a -> (a -> a)

This means that addFunc actually takes one argument and returns a function that takes another argument and returns an Int. In other words, addFunc is a function that takes a number and returns a function that takes a number and returns the sum of the two numbers.

-}

add9 :: Integer -> Integer
add9 = addFunc 9

onePlus9 :: Integer
onePlus9 = add9 1 

Prelude> onePlus9
10
Prelude> 

7. CONCLUSION

Haskell higher-order functions allow for powerful abstractions. They make it easier to think in terms of functions and design the ultimate abstraction of Embedded Domain Specific Languages (EDSLs).

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