HASKELL HIGHER ORDER FUNCTIONS

REVISED: Monday, February 12, 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 map using list comprehension makes it easy to see how 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 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 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 Embeded 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.

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.