» CS 330 Lecture 30 – Lambdas in Haskell and Composition

CS 330 Lecture 30 – Lambdas in Haskell and Composition

April 18, 2016 by Chris Johnson. Filed under cs330, lectures, spring 2016.

Agenda

what ?s
program this
lambdas in Haskell
associating with $
composing functions

TODO

On Wednesday night at 7 PM, I am giving a talk on Madeup at the Acoustic Cafe as part of the Ask a Scientist series. Attend and provide some proof of attendance (a sketch of me with one of the presented models, a soiled napkin, a receipt, a selfie with me, etc.) on Friday for two extra credit participation points.

Note

We’ve been discussing how lambdas let us create unnamed functions on the fly. This power becomes really, really useful the more we use higher-order functions to factor out a bunch of repeated code. We’ve examined them in Ruby (via blocks) and Java 8. Before seeing them in Haskell, let’s do a quick Program This:

Write in Java a static method forEach and any supporting code. This method applies some void routine to every element in the list given as a parameter.

Lambdas in Haskell

Haskell’s lambdas should contain few surprises, as they look a lot like Java 8’s. (Haskell had them first.) They roughly follow this syntactic pattern:

\param1, param2, param3 -> f param1, param2, param3

Lambda parameter lists are an opportunity to perform pattern matching. Suppose you know param1 is a non-empty list, whose only element you care about is the head.

\(first:_), param2, param3 -> f first, param2, param3

We’ll solve a few problems using lambdas:

mapping the natural numbers to the odds
filtering out all the strings of a certain length
extracting out all the first letters of words in a sentence

For this last one, we’ll see how we can use $ to control the association without flooding our expression with parentheses.

UFW

Once you know about lambdas, you may be tempted to overuse them. Suppose you want to add 1 to all the numbers in a list. You might write:

map (\x -> x + 1) [1..10]

But this is excessive. There are other ways to produce a function that adds 1 than lambdas. We could write this more simply using partial function application of the + function:

map (+1) [1..10]

Likewise, suppose you have a list of words and you want to extract all their first letters. You might write:

map (\word -> head word) ["alpha", "beta", "gimel"]

You lambda is a non-contributing wrapper around function head. You might as well eliminate the lambda altogether:

map head ["alpha", "beta", "gimel"]

Programming languages research Dan Grossman calls this UFW—unnecessary function wrapping.

Composition

We’ve seen that we can create functions several ways:

by defining a named function
by partially applying parameters to get a new function expecting only the remaining parameters
by defining unnamed lambdas

We’ll look at one final way: composition. What have your math classes taught you about composition? That f(g(x)) is a composition probably. Sometimes it’s nice to be able to roll that f and g together into one function h so that we can just say h(x). Haskell let’s use do just such a composition using the . operator. We’ll write a few compositions to perform the following tasks:

absmax
rsort
scalebias

As we have time, we’ll look at how we might compose functions in Java.

Code

ForEach.java

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in `to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute `gem env` for more information
	from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in `to_spec'
	from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in `gem'
	from ./coderay:24:in `'

fs.hs

import Data.List

odds = map (\x -> 2 * x + 1) [0..]

longs :: [String] -> [String]
longs = filter (\word -> length word > 4)

firstletters :: String -> String
firstletters sentence = map fst (filter (\(_, predecessor) -> predecessor == ' ') (zip sentence (' ' : sentence)))
-- firstletters sentence = map (\tuple -> fst tuple) (filter (\(_, predecessor) -> predecessor == ' ') (zip sentence (' ' : sentence)))

-- rsort l = reverse (sort l)
-- rsort l = (reverse . sort) l
rsort :: Ord a => [a] -> [a]
rsort = (reverse . sort)