proglang-09-12-19.md

Higher Order Functions & Lambdas - Programming Languages - Sep 12th, 2019

Higher Order Functions

A function that takes in a function as a parameter

• filter
• map
• foldl

Filter

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f [] = []
myfilter f (h:t) =
	if f h then 
		h : myfilter f t
	else
		myfilter f t

Map

mymap :: (a -> b) -> [a] -> [b]
mymap f [] = []
mymap f (h:t) = f h : mymap f t

Foldl

-- foldl (function) (default value) [list]
foldl (\x y -> x * y) 1 [1..5]

-- add up the length of strings in a list
foldl (\acc val -> acc + length val) 0 ["hi", "hello","foo"]

-- a is the type of elements to combine with accumlator
-- b is the type of the accumulator nad the result
myfoldl :: (b -> a -> b) -> b -> [a] -> b

Write max using foldl

-- Assume inputs are non-negative
mymax :: [Int] -> Int
mymax [] = error "You must give me a value"
mymax a  =
	foldl (\acc val -> if acc > val then acc else val) 0 a

Lambdas

“Double” function with lambda

map (\x -> x * 2) [10, 20, 30]
-- or
map (*2) [10,20,30] -- not a lambda
-- * is a function

Lambdas in Python

list(filter(lambda x: x+1, [1,2,3,4,5,6]))

isPrime & FindPrime

isPrime :: Int -> Bool
isPrime 2 = True
isPrime x = filter (\y -> (x `mod` y) == 0) [2..x `div` 2] == []

findPrimes [] = []
findPrimes x = filter isPrime 

Fibonacci

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
-- This is slow because you have redundant calculations

addList :: [Int] -> [Int] -> [Int]
addLists (h1:t1) (h2:t2) = (h1 + h2) : addLists t1 + t2

fibs :: [Int]
fibs = map fib [1..] -- This creates an infinite list

-- Better fibonacci
-- Run with: `take N fibs2`
fibs2 :: [Int]
fibs2 = [0,1] ++ addLists fibs2 (tail fibs2)

#proglang-f19