HW2 - Exercise 2

  /**
   * Problem 2: Reversed Binary Representation (5 points each)
   *
   * Implement the basic operations of reversed binary representation (RBB).
   * You should use the predefined `BNum` type from Data.scala file.
   *
   * RBB is one way to represent natural number through ADT.
   *
   * BHead: Most significant bit (1)
   * B1: One (1)
   * B0: Zero (0)
   *
   * e.g.)
   * number 1 -> BHead
   * number 6 -> /binarize/ 110 (2) -> /reverse/ 011 -> /RBB/ B0(B1(BHead))
   * number 11 -> /binarize/ 1011 (2) -> /reverse/ 1101 -> /RBB/ B1(B1(B0(BHead)))
   **/

  /**
   * Addition (a + b)
   * e.g.) add(B0(B1(BHead)), B0(BHead)) == B0(B0(B0(BHead))) // 6 + 2 = 8
   */
  def add(a: BNum, b: BNum): BNum = ???

  /**
   * Multiplication (a * b)
   * e.g.) mul(B0(B1(BHead)), B0(BHead)) == B0(B0(B1(BHead))) // 6 * 2 = 12
   */
  def mul(a: BNum, b: BNum): BNum = ???

  /**
   * Comparison (a > b)
   * e.g.) compare(B0(B1(BHead)), B0(BHead)) == 1 // 6 > 2
   *
   * return
   * | 1  (a > b)
   * | 0  (a == b)
   * | -1 (a < b)
   */
  def compare(a: BNum, b: BNum): Int = ???

 

 

 

 

 

 

2번째 문제

My Solution

 

sealed trait BNum
case object BHead extends BNum
case class B0(next: BNum) extends BNum
case class B1(next: BNum) extends BNum

sealed abstract class BList
case class BNil() extends BList
case class BCons(hd:Int,tl:BList) extends BList

def toList(x:BNum):BList ={
  x match{
    case BHead => BCons(1,BNil())
    case B0(next) => BCons(0,toList(next))
    case B1(next) => BCons(1,toList(next))}}
def toNum(y:BList):BNum ={
  y match{
    case BCons(1,BNil()) => BHead
    case BCons(1,tl) => B1(toNum(tl))
    case BCons(0,tl) => B0(toNum(tl))}}
def hdReader(x:BList):Int = {
  x match {
    case BCons(0,_)=>0
    case _ => 1}}
def tlReader(x:BList):BList={
  x match {
    case BCons(_,tl) => tl}}

def addBList(A: BList, B: BList, num: Int = 0): BList = {
  if ((A == BNil()) && (B == BNil())) {
    num match {
      case 1 => BCons(1, BNil())
      case 0 => BNil()}}

  else if (A == BNil()) {
    val sum = hdReader(B) + num
    sum match {
      case 2 => BCons(0, addBList(BNil(), tlReader(B), 1))
      case 1 => BCons(1, addBList(BNil(), tlReader(B)))
      case 0 => BCons(0, addBList(BNil(), tlReader(B)))}}

  else if (B == BNil()) {
    val sum = hdReader(A) + num
    sum match {
      case 2 => BCons(0, addBList(tlReader(A), BNil(), 1))
      case 1 => BCons(1, addBList(tlReader(A), BNil()))
      case 0 => BCons(0, addBList(tlReader(A), BNil()))}}

  else {
    val sum = hdReader(A) + hdReader(B) + num
    sum match {
      case 0 => BCons(0, addBList(tlReader(A), tlReader(B)))
      case 1 => BCons(1, addBList(tlReader(A), tlReader(B)))
      case 2 => BCons(0, addBList(tlReader(A), tlReader(B), 1))
      case 3 => BCons(1, addBList(tlReader(A), tlReader(B), 1))}}
}


def add(a: BNum, b: BNum): BNum = {
  val A:BList = toList(a)
  val B:BList = toList(b)
  toNum(addBList(A,B))}

def mul(a: BNum, b: BNum): BNum = {
  val A = toList(a); val B = toList(b)
  def mulList(A:BList, B:BList):BList ={
    hdReader(B) match {
      case 0 => BCons(0,mulList(A,tlReader(B)))
      case 1 => tlReader(B) match {
        case BNil() => A
        case _ => addBList(A,BCons(0,mulList(A,tlReader(B))))}}}
  toNum(mulList(A,B))}

def compare(a: BNum, b: BNum): Int = {
  def listToInt(x: BList): Int = {
    if (x == BNil()) 0
    else {
      hdReader(x) match {
        case 0 => 0 + 2 * listToInt(tlReader(x))
        case 1 => 1 + 2 * listToInt(tlReader(x))}}}
  val A = listToInt(toList(a)); val B=listToInt(toList(b))
  if (A>B) 1
  else if (A == B) 0
  else -1
}