fpis.scala

//> using lib "org.scalameta::munit:1.0.0-M6"

//@annotation.tailrec
def fib(n: Int): Int =
  if (n == 0) 0
  else if (n == 1) 1
  else fib(n - 1) + fib(n - 2)

def fib2(n: Int): Int =
  @annotation.tailrec
  def fibTail(n: Int, a: Int, b: Int): Int = n match
    case 0 => a
    case _ => fibTail(n - 1, b, a + b)
  return fibTail(n, 0, 1)

class TestSuiteFib extends munit.FunSuite {
  test("hello") {
    assertEquals(fib(0), 0)
    assertEquals(fib(1), 1)
    assertEquals(fib(2), 1)
    assertEquals(fib(3), 2)
    assertEquals(fib(4), 3)
    assertEquals(fib(5), 5)
    assertEquals(fib2(6), 8)
  }
}

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean =
  @annotation.tailrec
  def loop(as: Array[A]): Boolean =
    as.length <= 1 || (ordered(as(0), as(1)) && loop(as.tail))
  loop(as)

class TestSuiteIsSorted extends munit.FunSuite {
  test("happy path") {
    assertEquals(isSorted(Array[Int](), (x: Int, y: Int) => x <= y), true)
    assertEquals(isSorted(Array[Int](1), (x: Int, y: Int) => x <= y), true)
    assertEquals(
      isSorted(Array[Int](1, 2, 3), (x: Int, y: Int) => x <= y),
      true
    )
    assertEquals(
      isSorted(Array[Int](1, 3, 1), (x: Int, y: Int) => x <= y),
      false
    )
  }
}

def partial1[A, B, C](a: A, f: (a: A, b: B) => C): (b: B) => C = (b: B) =>
  f(a, b)
class TestSuitePartial1 extends munit.FunSuite {
  test("quadruple") {
    val quadruple = partial1(4, (a: Int, b: Int) => a * b)
    assertEquals(quadruple(10), 40)
  }
}

def curry[A, B, C](f: (A, B) => C): A => (B => C) =
  (a: A) => (b: B) => f(a, b)

val mul = (x: Int, y: Int) => x * y

class TestCurry extends munit.FunSuite {
  test("quadruple") {
    val mulCurried = curry(mul)
    val quadruple = mulCurried(4)
    assertEquals(quadruple(10), 40)
  }
}

def uncurry[A, B, C](f: A => B => C): (A, B) => C =
  (a: A, b: B) => f(a)(b)

class TestUncurry extends munit.FunSuite {
  test("quadruple") {
    val myMul = uncurry(curry(mul))
    assertEquals(myMul(4, 10), 40)
  }
}

def compose[A, B, C](f: B => C, g: A => B): A => C =
  (a: A) => f(g(a))

class TestComposition extends munit.FunSuite {
  test("Brouzoufs") {
    val int2string = (a: Int) => a.toString()
    val appendBrouzouf = (s: String) => s.appendedAll(" brouzouf")
    val nbBrouzouf = compose(appendBrouzouf, int2string)
    assertEquals(nbBrouzouf(1), "1 brouzouf")
  }
}

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
  def apply[A](xs: A*): List[A] =
    if xs.isEmpty then Nil
    else Cons(xs.head, apply(xs.tail: _*))

  def sum(xs: List[Int]): Int = xs match
    case Nil        => 0
    case Cons(h, t) => h + sum(t)

  def tail[A](xs: List[A]): List[A] = xs match
    case Nil        => Nil
    case Cons(x, t) => t

  def setHead[A](xs: List[A], h: A): List[A] = xs match
    case Nil        => Nil
    case Cons(x, t) => Cons(h, t)

  def drop[A](xs: List[A], n: Int): List[A] = xs match
    case Nil                 => Nil
    case Cons(x, t) if n > 0 => drop(t, n - 1)
    case _                   => xs

  def dropWhile[A](xs: List[A], pred: A => Boolean): List[A] = xs match
    case Nil                   => Nil
    case Cons(h, t) if pred(h) => dropWhile(t, pred)
    case _                     => xs

  def init[A](xs: List[A]): List[A] = xs match
    case Nil                   => Nil
    case Cons(x, Cons(y, Nil)) => Cons(x, Nil)
    case Cons(x, t)            => Cons(x, init(t))

  def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = as match {
    case Nil        => z
    case Cons(x, t) => f(x, foldRight(t, z)(f))
  }

  def sum2(ns: List[Int]) = foldRight(ns, 0)((x, y) => x + y)

  def product2(ns: List[Double]) = foldRight(ns, 1.0)(_ * _)

  def length[A](xs: List[A]): Int = foldRight(xs, 0)((x, n) => n + 1)

  @annotation.tailrec
  def foldLeft[A, B](as: List[A], z: B)(f: (B, A) => B): B = as match
    case Nil        => z
    case Cons(x, t) => List.foldLeft(t, f(z, x))(f)

  def append[A](l: List[A], appended: List[A]): List[A] =
    List.foldRight(l, appended)(Cons(_, _))

  def flatten[A](xs: List[List[A]]): List[A] =
    List.foldRight(xs, Nil: List[A])(List.append)

  def map[A, B](xs: List[A])(f: A => B): List[B] =
    foldRight(xs, Nil: List[B])((x, acc) => Cons(f(x), acc))

  def filter[A](xs: List[A])(pred: A => Boolean) =
    foldRight(xs, Nil: List[A])((x: A, acc: List[A]) =>
      if pred(x) then Cons(x, acc) else acc
    )

  def flatMap[A](xs: List[A])(f: (x: A) => List[A]) =
    foldLeft(xs, Nil: List[A])((acc: List[A], x: A) => append(acc, f(x)))
    // foldRight(xs, Nil:List[A])(( x:A, acc:List[A]) => append(acc, f(x)))

  def zipWith[A, B, C](xs1: List[A], xs2: List[B])(
      combine: (A, B) => C
  ): List[C] =
    assert(List.length(xs1) == List.length(xs2))
    @annotation.tailrec
    def loop(xs1: List[A], xs2: List[B], acc: List[C]): List[C] =
      xs1 match
        case Nil => acc
        case Cons(h1, t1) =>
          xs2 match
            case Cons(h2, t2) => loop(t1, t2, Cons(combine(h1, h2), acc))
            case _            => Nil
    loop(xs1, xs2, Nil: List[C])

  @annotation.tailrec
  def startswith[A](sup: List[A], sub: List[A]): Boolean = sub match
    case Nil => true
    case Cons(xSub, tSub) =>
      sup match
        case Nil => false // case where sup.length < sub.length
        case Cons(xSup, tSup) if xSub != xSup => false
        case Cons(_, tSup)                    => startswith(tSup, tSub)

  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean =
    @annotation.tailrec
    def loop[A](sup: List[A], sub: List[A]): Boolean = sup match
      case Nil                                => false
      case Cons(_, _) if startswith(sup, sub) => true
      case Cons(_, tSup)                      => loop(tSup, sub)
    loop(sup, sub)

}

class TestList extends munit.FunSuite {
  test("pattern matching") {
    val x = List(1, 2, 3, 4, 5) match
      case Cons(x, Cons(4, _))                   => x
      case Nil                                   => 42
      case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y // first match
      case Cons(h, t)                            => h + List.sum(t) // match
      case null                                  => 101
    assertEquals(x, 3)
  }

  test("apply") {
    val l = List(Seq(1, 2, 3, 4, 5): _*)
    assertEquals(l, List(1, 2, 3, 4, 5))
  }

  test("tail") {
    val l = List(1, 2, 3, 4, 5)
    assertEquals(List.tail(l), List(2, 3, 4, 5))
  }

  test("tail nil") {
    assertEquals(List.tail(Nil), Nil)
  }

  test("setHead") {
    assertEquals(List.setHead(List(1, 2), 3), List(3, 2))
  }

  test("setHead nil") {
    assertEquals(List.setHead(Nil, 2), Nil)
  }

  test("drop nil") {
    assertEquals(List.drop(Nil, 111), Nil)
  }

  test("drop all") {
    assertEquals(List.drop(List(1), 2000), Nil)
  }

  test("drop some") {
    assertEquals(List.drop(List(1, 2, 3), 2), List(3))
  }

  test("drop negative") {
    assertEquals(List.drop(List(1, 2, 3), -2), List(1, 2, 3))
  }

  val lt2 = (x: Int) => x < 2

  test("dropWhile") {
    assertEquals(List.dropWhile(Nil, lt2), Nil)
    assertEquals(List.dropWhile(List(1, 1), lt2), Nil)
    assertEquals(List.dropWhile(List(1, 2, 3), lt2), List(2, 3))
    assertEquals(List.dropWhile(List(3, 4), lt2), List(3, 4))

  }

  test("init") {
    assertEquals(List.init(List(1, 2, 3)), List(1, 2))
  }

  test("exercice 3.8") {
    val x = List.foldRight(List(1, 2, 3), Nil: List[Int])(Cons(_, _))
    assertEquals(x, List(1, 2, 3))
    // What do you think this says about the relationship between foldRight and the data constructors of List?
    // ???
  }

  test("length") {
    assertEquals(List.length(List(1, 2, 3)), 3)
  }

  test("foldLeft") {
    // sum
    assertEquals(List.foldLeft(List(1, 2, 3, 4), 0)(_ + _), 10)
    // product
    assertEquals(List.foldLeft(List(1, 2, 3, 4), 1)(_ * _), 24)
    // length
    assertEquals(List.foldLeft(List(1, 2, 3, 4), 0)((acc, _) => acc + 1), 4)
    // reverse
    val l = List(1, 3, 4)
    val init: List[Int] = Nil
    val reversed =
      List.foldLeft(l, init)((acc: List[Int], x: Int) => Cons(x, acc))
    assertEquals(reversed, List(4, 3, 1))
    // Implement append in terms of either foldLeft or foldRight.
    assertEquals(List.append(l, List(6, 7)), List(1, 3, 4, 6, 7))
    // Write a function that concatenates a list of lists
    assertEquals(List.flatten(List(l, List(6, 7))), List(1, 3, 4, 6, 7))
  }

  test("map") {
    assertEquals(List.map(List(1, 2, 3))(_ + 1), List(2, 3, 4))
  }

  test("filter") {
    assertEquals(List.filter(List(1, 2, 3))(_ % 2 == 0), List(2))
  }

  test("flatMap") {
    assertEquals(
      List.flatMap(List(1, 2, 3))(i => List(i, i + 1)),
      List(1, 2, 2, 3, 3, 4)
    )

    // filter with flatmap
    def pred(x: Int) = x % 2 == 0
    assertEquals(
      List.flatMap(List(1, 2, 3))(i => if pred(i) then List(i) else Nil),
      List(2)
    )
  }

  test("zipWith") {
    assertEquals(
      List.zipWith(List(1, 2, 3), List(1, 2, 3))(_ - _),
      List(0, 0, 0)
    )
  }

  test("startsWith") {
    assertEquals(
      List.startswith(List(1, 2, 3), List(1, 2)),
      true
    )
    // TODO more tests ...
  }

  test("hasSubsequence") {
    assertEquals(
      List.hasSubsequence(List(1, 2, 3), List(2, 3)),
      true
    )
  }

}

import munit.Clue.generate

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {
  def size[A](t: Tree[A]): Int =
    def loop(t: Tree[A]): Int =
      t match
        case Leaf(_)             => 1
        case Branch(left, right) => 1 + loop(left) + loop(right)
    loop(t)

  def maximum(t: Tree[Int]): Int =
    def loop(t: Tree[Int]): Int =
      t match
        case Leaf(v)      => v
        case Branch(l, r) => loop(l).max(loop(r))
    loop(t)

  def depth[A](t: Tree[A]): Int =
    def loop(t: Tree[A]): Int = t match
      case Leaf(_)      => 1
      case Branch(l, r) => 1 + loop(l).max(loop(r))
    loop(t)

  def map[A, B](t: Tree[A])(f: A => B): Tree[B] = {
    t match
      case Leaf(v)      => Leaf(f(v))
      case Branch(l, r) => Branch(map(l)(f), map(r)(f))
  }

  def fold[A, B](t: Tree[A], onleaf: (A) => B, onbranch: (B, B) => B): B =
    def loop(t: Tree[A]): B =
      t match
        case Leaf(v) => onleaf(v)
        case Branch(left, right) => {
          val leftv = loop(left)
          val rightv = loop(right)
          onbranch(leftv, rightv)
        }
    loop(t)
}

class TestTree extends munit.FunSuite {
  val t: Tree[Int] = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
  test("size") {
    assertEquals(Tree.size(t), 5)
  }
  test("max") {
    assertEquals(Tree.maximum(t), 3)
  }
  test("depth") {
    assertEquals(Tree.depth(t), 3)
  }
  test("map") {
    assertEquals(
      Tree.map(t)(_.toString()),
      Branch(Leaf("1"), Branch(Leaf("2"), Leaf("3")))
    )
  }
  test("fold") {
    // size
    assertEquals(
      Tree.fold(
        t,
        (v: Int) => 1,
        (leftSize: Int, rightSize: Int) => { leftSize + rightSize + 1 }
      ),
      5
    )
    // maximum
    assertEquals(
      Tree.fold(
        t,
        (v: Int) => v,
        (leftSize: Int, rightSize: Int) => leftSize.max(rightSize)
      ),
      3
    )
    // depth
    assertEquals(
      Tree.fold(
        t,
        (v: Int) => 1,
        (leftSize: Int, rightSize: Int) => 1 + leftSize.max(rightSize)
      ),
      3
    )
    // map
    // TODO this won't compile, I don't know why
    // def map[A,B](t:Tree[A])(f:(A)=>B):Tree[B] =
    //  Tree.fold(t, (v:Int) => Leaf(f(v)), (l:Tree[B], r:Tree[B]) => Branch(l,r))
    // assertEquals( map(t)(_.toString()),  Branch(Leaf("1"), Branch(Leaf("2"), Leaf("3"))))

  }

}

sealed trait Option[+A] {
  def map[B](f: A => B): Option[B]
  def flatMap[B](f: A => Option[B]): Option[B]
  def getOrElse[B >: A](default: => B): B
  def orElse[B >: A](ob: => Option[B]): Option[B]
  def filter(f: A => Boolean): Option[A]
}

object Option:
  def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
    a.flatMap(x => b.map(y => f(x, y)))

  def sequence[A](xs: List[Option[A]]): Option[List[A]] = xs match
    case Nil => Some(Nil)
    case Cons(None,t) => None
    case Cons(Some(x), t) => map2(Some(x), sequence(t))(Cons.apply)
    

case class Some[+A](get: A) extends Option[A] {
  def map[B](f: A => B): Option[B] = Some(f(get))
  def flatMap[B](f: A => Option[B]): Option[B] = f(get)
  def getOrElse[B >: A](default: => B): B = get
  def orElse[B >: A](ob: => Option[B]): Option[B] = this
  def filter(f: A => Boolean): Option[A] = if (f(get)) then this else None
}

case object None extends Option[Nothing] {
  def map[B](f: Nothing => B): Option[B] = this
  def flatMap[B](f: Nothing => Option[B]): Option[B] = this
  def getOrElse[B](default: => B): B = default
  def orElse[B](ob: => Option[B]): Option[B] = ob
  def filter(f: Nothing => Boolean): Option[Nothing] = this
}

class TestOption extends munit.FunSuite {
  val s = Some(1)
  val n = None: Option[Int]
  test("map") {
    assertEquals(n.map(_.toString()), None)
    assertEquals(s.map(_.toString()), Some("1"))
  }
  test("flatmap") {
    assertEquals(n.flatMap(x => Some(x.toString())), None)
    assertEquals(s.flatMap(x => Some(x.toString())), Some("1"))
  }
  test("getOrElse") {
    assertEquals(n.getOrElse(33), 33)
    assertEquals(s.getOrElse(33), 1)
  }
  test("orElse") {
    assertEquals(n.orElse(Some(33)), Some(33))
    assertEquals(s.orElse(Some(33)), s)
  }
  test("filter") {
    assertEquals(n.filter(_ % 2 == 0), n)
    assertEquals(s.filter(_ % 2 == 0), n)
    assertEquals(Some(2).filter(_ % 2 == 0), Some(2))
  }

  test("variance") {
    def mean(xs:Seq[Double]): Option[Double] =
        if xs.isEmpty then  None else Some(xs.foldLeft(0d)(_ + _) / xs.length)

    def variance(xs: Seq[Double]): Option[Double] =
      mean(xs).flatMap(m => mean(xs.map(x => math.pow(x - m, 2))))
    

    assertEquals(variance(Seq(1,2,3)), Some(0.6666666666666666))
  }

  test("map2") {
    def hex_rem(a:Int, b:Int) = (a + b) % 16
    assertEquals(Option.map2(None, None)(hex_rem), None) 
    assertEquals(Option.map2(None, Some(1))(hex_rem), None) 
    assertEquals(Option.map2(Some(1), None)(hex_rem), None) 
    assertEquals(Option.map2(Some(8), Some(8))(hex_rem), Some(0)) 
  }

  test("sequence") {
    assertEquals(Option.sequence(List(Some(1), Some(2), Some(3))), Some(List(1,2,3)))
    assertEquals(Option.sequence(List(None, Some(2), Some(3))), None)
    assertEquals(Option.sequence(List(Some(1), None, Some(3))), None)
    assertEquals(Option.sequence(List(Some(1), Some(2), None)), None)
    assertEquals(Option.sequence(List()), Some(Nil))
  }
}