MyList (https://github.com/chatwork/scala-quiz/blob/master/quiz/04_MyList.md)

MyList.scala

package com.chatwork.quiz.collection

import com.chatwork.quiz.{MySome, MyNone, MyOption}

import scala.annotation.tailrec


sealed trait MyList[+A] {

  // Easy
  def length: Int = {
    @tailrec
    def go(list: MyList[A], acc: Int): Int = list match {
      case MyNil => acc + 0
      case MyCons(a, as) => go(as, acc + 1)
    }

    go(this, 0)
  }

  // Normal
  def foldLeft[B](z: B)(f: (B, A) => B): B = {
    @tailrec
    def go(l: MyList[A], acc: B): B = l match {
      case MyNil =>
        acc
      case MyCons(a, as) =>
        go(as, f(acc, a))
    }

    go(this, z)
  }

  // 難易度選択制
  // Normal: 条件 - 特にありません、気の向くままに実装してください。
  // Hard:   条件 - foldLeftを使って実装してください。
  def foldRight[B](z: B)(f: (A, B) => B): B =
    this.foldLeft((b: B) => b)((g, a) => b => g(f(a, b)))(z)

  // Normal
  // scalastyle:off
  def ::[B >: A](b: B): MyList[B] = MyCons(b, this)
  // scalastyle:on

  // Normal
  def reverse: MyList[A] = {
    @tailrec
    def go(acc: MyList[A], l: MyList[A]): MyList[A] = l match {
      case MyNil =>
        acc
      case MyCons(a, as) =>
        go(MyCons(a, acc), as)
    }

    go(MyNil, this)
  }

  // Normal
  // scalastyle:off
  def ++[B >: A](b: MyList[B]): MyList[B] = {
    @tailrec
    def go(acc: MyList[B], l: MyList[A]): MyList[B] = l match {
      case MyNil =>
        acc
      case MyCons(a, as) =>
        go(MyCons(a, acc), as)
    }

    go(b, this.reverse)
  }
  // scalastyle:on

  // Normal
  def map[B](f: A => B): MyList[B] = {
    @tailrec
    def go(acc: MyList[B], l: MyList[A]): MyList[B] = l match {
      case MyNil =>
        acc
      case MyCons(a, as) =>
        go(MyCons(f(a), acc), as)
    }

    go(MyNil, this)
  }

  // Normal
  def flatMap[B](f: A => MyList[B]): MyList[B] = {
    @tailrec
    def go2(acc: MyList[B], l: MyList[A]): MyList[B] = l match {
      case MyNil =>
        acc
      case MyCons(a, as) =>
        go2(acc ++ f(a), as)
    }

    go2(MyNil, this)

    /*
        @tailrec
        def go(acc: MyList[MyList[B]], l: MyList[A]): MyList[MyList[B]] = l match {
          case MyNil =>
            acc
          case MyCons(a, as) =>
            go(MyCons(f(a), acc), as)
        }

        val nested = go(MyNil, this)

        @tailrec
        def flatten(acc: MyList[B], l: MyList[MyList[B]]): MyList[B] = l.reverse match {
          case MyNil =>
            acc
          case MyCons(bs, bss) =>
            flatten(bs ++ acc, bss)
        }

        flatten(MyNil, nested)
    */
  }

  // Normal
  def filter(f: A => Boolean): MyList[A] = {
    @tailrec
    def go(acc: MyList[A], l: MyList[A]): MyList[A] = l match {
      case MyNil =>
        acc
      case MyCons(a, as) =>
        go(if (f(a)) MyCons(a, acc) else acc, as)
    }

    go(MyNil, this)
  }

  // Normal: 条件 - filterと同様の実装でも構いません。
  // Hard:   条件 - 中間リストを生成しないように実装してください。
  def withFilter(f: A => Boolean): MyList[A] = this.filter(f)

  // Normal
  def find(f: A => Boolean): MyOption[A] = {
    @tailrec
    def go(l: MyList[A]): MyOption[A] = l match {
      case MyNil =>
        MyNone
      case MyCons(a, as) =>
        if (f(a))
          MySome(a)
        else
          go(as)
    }

    go(this)
  }

  // Normal
  def startsWith[B >: A](prefix: MyList[B]): Boolean = {
    @tailrec
    def go(la: MyList[A], lb: MyList[B]): Boolean = lb match {
      case MyNil =>
        true
      case MyCons(b, bs) =>
        la match {
          case MyNil =>
            false
          case MyCons(a, as) =>
            go(as, bs)
        }
    }

    go(this, prefix)
  }
}

case object MyNil extends MyList[Nothing]

case class MyCons[+A](head: A, tail: MyList[A]) extends MyList[A]

object MyList {

  // Easy
  def empty[A]: MyList[A] = MyNil

  // Normal
  def apply[A](as: A*): MyList[A] = {
    @tailrec
    def go(acc: MyList[A], aa: A*): MyList[A] = {
      if (aa.length < 1)
        acc
      else
        go(MyCons(aa.last, acc), aa.init: _*)
    }

    go(MyNil, as: _*)
  }
}