quiz

MyList.scala

package com.chatwork.quiz.collection

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

// FIXME: MyNil、MyConsを使ってる場所はそれぞれのクラスでやるべきでは？
// FIXME: ifをなんとかしたい

sealed trait MyList[+A] {

  // Easy
  def length: Int = foldLeft(0)((z, _) => z + 1)

  // Normal
  // FIXME: finalをつけないと末尾再帰にならない...
  final def foldLeft[B](z: B)(f: (B, A) => B): B = this match {
    case MyNil => z
    case MyCons(head, tail) => tail.foldLeft(f(z, head))(f)
  }

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

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

  // Normal
  def reverse: MyList[A] = foldLeft(MyList.empty[A])((b, a) => a :: b)

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

  // Normal
  def map[B](f: A => B): MyList[B] = foldRight(MyList.empty[B])((a, b) => MyCons(f(a), b))

  // Normal
  def flatMap[B](f: A => MyList[B]): MyList[B] = foldRight(MyList.empty[B])((a, b) => f(a).foldRight(b)(_ :: _))

  // Normal
  def filter(f: A => Boolean): MyList[A] = foldRight(MyList.empty[A])((a, b) => if (f(a)) a :: b else b )

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

  // Normal
  def find(f: A => Boolean): MyOption[A] = this match {
    case MyNil => MyNone
    case MyCons(head, tail) => if (f(head)) MyOption(head) else tail.find(f)
  }

  // Normal
  def startsWith[B >: A](prefix: MyList[B]): Boolean = (this, prefix) match {
    case (_, MyNil) => true
    case (MyNil, _) => false
    case (MyCons(head1, tail1), MyCons(head2, tail2)) => head1 == head2 && tail1.startsWith(tail2)
  }

}

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] = as.foldRight(empty[A])(MyCons(_, _))

}

MyOption.scala

package com.chatwork.quiz

import com.chatwork.quiz.collection.MyNil

import scala.util.{Failure, Try}

/**
 * 値が存在する・しないの両状態を表すオブジェクト。いわゆるMaybeモナド。
 *
 * @tparam A 値の型
 */
sealed trait MyOption[+A] {

  /**
   * 格納された値を返す。
   *
   * @return 値
   * @throws 値が存在しない場合 NoSuchElementException をスローする
   */
  def get: A

  /**
   * 値がないかどうかを返す。
   *
   * @return 値が存在しない場合はtrue。
   */
  def isEmpty: Boolean

  /**
   * 値が存在する場合に、値の変換を行う。
   *
   * @param f 値を変換するための関数
   * @tparam B 新しい型
   * @return 新しい [[MyOption]]
   */
  def map[B](f: A => B): MyOption[B] = Try(MyOption(f(get))).recover {
    case _ => MyNone
  }.get

  /**
   * 値が存在する場合に、値の変換を行う。
   *
   * @param f 値を変数するための関数
   * @tparam B 新しい型
   * @return 新しい [[MyOption]]
   */
  def flatMap[B](f: A => MyOption[B]): MyOption[B] = Try(f(get)).recover {
    case _ => MyNone
  }.get

  /**
   * 値が存在する場合に、値をフィルタリングする。
   *
   * @param f フィルターのための述語関数
   * @return 新しい [[MyOption]]
   */
  def filter(f: A => Boolean): MyOption[A] = flatMap((a) => if (f(a)) MySome(a) else MyNone)

  /**
   * 格納された値を返す。値がない場合は指定された値を返す。
   *
   * @param elseValue 値がない場合に返す値
   * @tparam B 新しい要素型
   * @return 値
   */
  def getOrElse[B >: A](elseValue: B): B = Try(get).recover {
    case _ => elseValue
  }.get

  /**
   * 値が存在しない場合に、指定した式を評価し返す。
   *
   * @param elseValue 値が存在しない場合に返す式
   * @tparam B 新しい要素型
   * @return elseValueを評価した値
   */
  def orElse[B >: A](elseValue: => MyOption[B]): MyOption[B] = Try(MySome(get)).recover {
    case _ => elseValue
  }.get

}

/**
 * 値が存在ない場合の[[MyOption]]。
 */
case object MyNone extends MyOption[Nothing] {

  def get: Nothing = throw new NoSuchElementException

  def isEmpty: Boolean = true

}

/**
 * 値が存在する場合の[[MyOption]]。
 *
 * @param value 値
 * @tparam A 値の型
 */
case class MySome[+A](value: A) extends MyOption[A] {

  def get: A = value

  def isEmpty: Boolean = false

}

/**
 * [[MyOption]]のコンパニオンオブジェクト。
 */
object MyOption {

  /**
   * ファクトリメソッド。
   *
   * @param value 値
   * @tparam A 値の型
   * @return [[MyOption]]
   */
  def apply[A](value: A): MyOption[A] = if (value == null) MyNone else MySome(value)

}