Skip to content

Instantly share code, notes, and snippets.

@mattlong
Last active August 29, 2015 14:07
Show Gist options
  • Save mattlong/9416571ace0db598577b to your computer and use it in GitHub Desktop.
Save mattlong/9416571ace0db598577b to your computer and use it in GitHub Desktop.
foldLeft in terms of foldRight expansion
def foldRight[A,B](l: List[A], z: B)(f: (A, B) => B): B =
l match {
case Nil => z
case Cons(a, as) => f(a, foldRight(as, z)(f))
}
def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B =
foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)
foldLeft(List(1,2), 0)(_ + _)
// foldLeft rewritten in terms of foldRight
// A = Int
// B = (Int => Int)
// (_ + _) = f(_,_)
foldRight(List(1,2), (i:Int) => i)((x:Int, g: Int => Int) => (i:Int) => g(f(i,x)))(0)
//---Recurse---
// x = 1
((j:Int) => g(f(j,1)))(0)
// g = foldRight(List(2), (i:Int) => i)((x:Int, g: Int => Int) => (i:Int) => g(f(i,x)))
((j:Int) => foldRight(List(2), (i:Int) => i)((x:Int, g: Int => Int) => (i:Int) => g(f(i,x)))(f(j,1)))(0)
//---Recurse---
// x = 2
((j:Int) => ((k:Int) => g(f(k,2)))(f(j,1)))(0)
//g = foldRight(Nil, (i:Int) => i)((x:Int, g: Int => Int) => (i:Int) => g(f(i,x)))
((j:Int) => ((k:Int) => foldRight(Nil, (i:Int) => i)((x:Int, g: Int => Int) => (i:Int) => g(f(i,x)))(f(k,2)))(f(i,1)))(0)
//---Recurse---
// z = (i:Int) => i
((j:Int) => ((k:Int) => ((i:Int) => i)(f(k,2)))(f(j,1)))(0)
//---Apply and Simplify---
// j = 0
((k:Int) => ((i:Int) => i)(f(k,2)))(f(0,1))
// k = f(0,1)
((i:Int) => i)(f(f(0,1),2))
// i = f(f(0,1),2)
f(f(0,1),2)
// f = (_ + _)
f((0 + 1), 2)
// f = (_ + _)
((0 + 1) + 2)
// looks like foldleft to me!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment