Scribd
Upload
4 views7 pages

Haskell Higher-Order Functions Explained

This document discusses folding in Haskell using the higher-order functions foldr and foldl. Foldr folds a list from right to left by recursively applying a reduction function to each element and the accumulated result, starting from the right. Foldl folds a list from left to right by recursively applying the reduction function to the accumulated result and each element, starting from the left. The document provides examples of implementing insertion sort using foldr and explains how foldr and foldl differ in how they evaluate and whether they can terminate on infinite lists.

Uploaded by

markydee_20
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views7 pages

Haskell Higher-Order Functions Explained

This document discusses folding in Haskell using the higher-order functions foldr and foldl. Foldr folds a list from right to left by recursively applying a reduction function to each element and the accumulated result, starting from the right. Foldl folds a list from left to right by recursively applying the reduction function to the accumulated result and each element, starting from the left. The document provides examples of implementing insertion sort using foldr and explains how foldr and foldl differ in how they evaluate and whether they can terminate on infinite lists.

Uploaded by

markydee_20
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CPSC449&

Programming&Paradigms&

Fold&Example&
(Haskell)&
&

Dr.&Robert&Collier&
Spring&2015&

Modified'by'
Arash'Afshar'

HigherDOrder&Functions&and&Folding&

foldr&(from&Prelude)&is&a&HigherDOrder&Function&&
it&takes&a&Reduction&(and&an&Identity)&as&an&Argument&
&
the&r&in&foldr&means&Folding&to&the&Right&
&
How&is&it&Implemented?&
&
&foldr&::&(a&*>&b&*>&b)&*>&b&*>&[a]&*>&b&
&foldr&op&id&[]&=&id&
&foldr&op&id&(h:t)&
& &=&(op&h&(foldr&op&id&t))&
2&

Insertion&Sort&Revisited&

How&do&you&Implement&Insertion&Sort&Using&foldr?&
&
insert&::&Int&*>&[Int]&*>&[Int]&
insert&x&[]&=&[x]&
insert&x&(h:t)&
&|&x&<=&h&=&x:(h:t)&
&|&otherwise&=&h:(insert&x&t)&
&
insertSort'&::&[Int]&*>&[Int]&
insertSort'&x&=&foldr&insert&[]&x&&
&
3&

Insertion&Sort&Revisited&

insertSort'&[3,2,1]&
~>&foldr&insert&[]&[3,2,1]&
~>&insert&3&(foldr&insert&[]&[2,1])&
~>&insert&3&(insert&2&(foldr&insert&[]&[1]))&
~>&insert&3&(insert&2&(insert&1&(foldr&
insert&[]&[])))&
~>&insert&3&(insert&2&(insert&1&([])))&
~>&insert&3&(insert&2&([1]))&
~>&insert&3&([1,2])&
~>&1:(insert&3&[2])&
>> 1:2:(insert 3 [])
~>&...& >> 1:2:3:[]
~>&[1,2,3]&

4&

HigherDOrder&Functions&and&Folding&

foldl&(from&Prelude)&is&a&HigherDOrder&Function&&
it&takes&a&Reduction&(and&an&Identity)&as&an&Argument&
&
the&l&in&foldl&means&Folding&to&the&Left&
Here, the base case involves the leftmost element.
&
The first thing evaluated is the operator and the head of the list.
How&is&it&Implemented?&
&
&foldl&::&(a&*>&b&*>&b)&*>&b&*>&[a]&*>&b&
&foldl&op&z&&[]&=&z&
&foldl&op&id&(h:t)&
& &=&foldl&op&(op&id&h)&t&
If the list is empty, the result is the initial value z.
If not, fold the tail of the list using as new initial value which is
the result of applying op to the old initial value and the first element.

5&

Comparison&

foldr&opr&id&a:b:c:d:e:&expands&to&
&
a&`opr`&(b&`opr`&(c&`opr`&(...&`op`&id)))&
opr
& a (opr b (opr c (. . . opr id . . .)))
&
foldl&opl&id&a:b:c:d:e:&expands&to&
&
(((id&`opl`&a)&`opl`&b)&`opl`&c)&`opl`&...&

6&

Comparison&

Given&an&innite&list&as&input,&
&
foldr&has&a&chance&of&terminating&if&op&can&terminate&
on&an&innite&list&
&
foldl&will&never&terminate&since&the&recursion&depends&
on&foldl&and&the&input&list&regardless&of&the&op&

7&

You might also like