Folding Code Kata

Based on 'Folding Unfolded - Polyglot FP for Fun and Profit - Haskell and Scala - Part 1' and 'Folding Unfolded - Polyglot FP for Fun and Profit - Haskell and Scala - Part 2'

1. Implement foldr (right fold) and foldl (left fold) - (optional - skip this initially and return to it later)

   • Fold Problem
   • Fold Solution

2. Practice implementing a number of simple functions using recursion, foldr and foldl. For each function, e.g. length, there is a problem Scala file where you can implement the function by filling in the code marked by ???, and a solution Scala file in which you can see a ready-made implementation. Both files contain assertions that get executed when you run the App contained in the file.

   • Length Problem
   • Length Solution
   • Sum Problem
   • Sum Solution
   • Concatenate Problem
   • Concatenate Solution
   • Concat Problem
   • Concat Solution
   • Reverse Problem
   • Reverse Solution
   • Map Problem
   • Map Solution
   • Decimal Problem
   • Decimal Solution

3. See examples of the three fold duality theorems in action

   • First Duality Theorem
     • foldr (⊕) e xs = foldl (⊕) e xs
     • for all finite lists xs
     • if x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z
     • and x ⊕ e = e ⊕ x
   • Second Duality Theorem
     • foldr (⊕) e xs = foldl (⊗) e xs
     • for all finite lists xs
     • if x ⊕ (y ⊗ z) = (x ⊕ y) ⊗ z
     • and x ⊕ e = e ⊗ x
   • Third Duality Theorem
     • foldr f e xs = foldl (flip f) e (reverse xs)
     • where flip f x y = f y x

4. See all solutions and theorem examples in a single file

   • All Solutions and Theorem Examples

Sample file contents

Problem File Example: _01_Length_Problem.scala

import _00_Fold_Solution.{foldl, foldr}

object _01_Length extends App {

 // length ∷ [α] → Int
 // length [] = ???
 // length (x:xs) = ???   
 def length[A]: List[A] => Int = {
   case Nil     => ???
   case x :: xs => ???
 }
 assert(length(List()) == 0)
 assert(length(List(1, 2, 3)) == 3)
 
 // length ∷ [α] → Int
 // length = foldr ??? ???
 { def length[A]: List[A] => Int = foldr(???)(???)
   assert(length(List()) == 0)
   assert(length[Int](List(1, 2, 3)) == 3) }
 
 def oneplus[A]: A => Int => Int =
   x => n => ???
 
 // length ∷ [α] → Int
 // length = foldl ??? ???
 { def length[A]: List[A] => Int = foldl(???)(???)
   assert(length(List()) == 0)
   assert(length[Int](List(1, 2, 3)) == 3) }
 
 def plusOne[A]: Int => A => Int =
   n => x => ???
}

Solution File Example: _01_Length_Solution.scala

import _00_Fold_Solution.{foldr,foldl}

object _01_Length_Solution extends App {

  // length ∷ [α] → Int
  // length [] = 0
  // length (x:xs) = 1 + length xs
  def length[A]: List[A] => Int = {
    case Nil     => 0
    case x :: xs => 1 + length(xs)
  }
  assert(length(List()) == 0)
  assert(length(List(1, 2, 3)) == 3)

  // length ∷ [α] → Int
  // length = foldr oneplus 0
  { def length[A]: List[A] => Int = foldr(oneplus)(0)
    assert(length(List()) == 0)
    assert(length[Int](List(1, 2, 3)) == 3) }

  def oneplus[A]: A => Int => Int =
    x => n => 1 + n

  // length ∷ [α] → Int
  // length = foldl plusone 0
  { def length[A]: List[A] => Int = foldl(plusOne)(0)
    assert(length(List()) == 0)
    assert(length[Int](List(1, 2, 3)) == 3) }

  def plusOne[A]: Int => A => Int =
    n => x => n + 1
}