Matrix Algebra and type level programming ~> compile time checks?

mat.scala

/*
First implementation of a Matrix String Interpolator.
This is a manipulable matrix strucutre

mat"""
  | 1  |  2
  | 3  |  
"""
*/
object Mat {
  def indexesOf(p:Char=>Boolean)(s:String):Seq[Int] = {
    s.zipWithIndex.foldLeft(Nil:Seq[Int]) { case (xs, (ch, i))  =>
      if (p(ch)) {
        i +: xs  
      } else {
        xs
      }
    }.reverse
  }
  val indexesOfPipe = indexesOf(_ == '|') _

  def ranges(xs:Seq[Int])= {
    xs.init zip xs.tail
  }

  val toInt = (s:String) => if (s.isEmpty) None else Some(s.toInt)

  def extractParts[A](m:String => Option[A], missing: A)(s:String):Seq[A] = {
    val rs = ranges(indexesOfPipe(s) ++: s.length +: Nil)
    rs.map { case (st, en) =>
      m(s.slice(st, en).tail.trim).getOrElse(missing)
    }
  }

  implicit class MatHelper(val sc: StringContext) extends AnyVal {
    def mat(args: Any*): Seq[Seq[Int]] = {
      val r = sc.s(args:_*) //skip first line
      val rows = r.lines.filter(!_.trim.isEmpty)
      val extractIntMissingAsZero = extractParts(toInt, 0) _
      val cells = rows.map(extractIntMissingAsZero).toSeq
  
      cells
    }
  }

  val a00 = 1

  val s = mat"""
    | $a00 | 3     |  1 
    | 1    |       |   
    |      | $a00  |  1 
  """

  val i00 = 1
  val id = mat"""
    | $i00 |       |  
    |      | $i00  |   
    |      |       |  1 
  """

  def apply() = {
    println(s.toList)
    
    println(id.toList)
    
    println(test("""
        

      | 1    |       |  
      |      | 1     |   



      |      |       |  1 
    """))
  }

  def test(s:String) = {
    val x = mat"$s"
    x.toList
  }


}

tl.scala

/*
My work-in-progress learning-code of Type Level Programming (using http://apocalisp.wordpress.com/2010/06/08/type-level-programming-in-scala/)
I'll try to combine this with "mat.scala"  to allow visual matrices algebra (shaped Strings) with compiled time (using type System) dimensions checks.
 
"""
  | 1  |  2
  | 3  |  
""" x
       """
          | 4 | 5
       """
Shouldn't compile because 2x2 cannot be mult by 1x2
*/
sealed trait Bool {
  type If[T <: Up, F <: Up, Up] <: Up
 
}
sealed trait True extends Bool {
  type If[T <: Up, F <: Up, Up] = T
}
sealed trait False extends Bool {
  type If[T <: Up, F <: Up, Up] = F
}
 
object Bool {
  type &&[U <: Bool, V <: Bool] = U#If[V, False, Bool]
  type ||[U <: Bool, V <: Bool] = U#If[True, V, Bool]
  type ~[U <: Bool] = U#If[False, True, Bool]
 
  def toBoolean[B <: Bool](implicit b:BoolRep[B]):Boolean = b.value
  class BoolRep[B <: Bool](val value:Boolean)
  implicit val TrueRep = new BoolRep[True](true)
  implicit val FalseRep = new BoolRep[False](false)
}
 
/**
 * Comparison
 */
sealed trait Comparison {
  type Match[IfLT <: Up, IfEQ <: Up, IfGT <: Up, Up] <: Up
 
  type gt = Match[False, False, True, Bool]
  type ge = Match[False, True, True, Bool]
  type eq = Match[False, True, False, Bool]
  type lt = Match[True, False, False, Bool]
  type le = Match[True, True, False, Bool]
}
sealed trait GT extends Comparison {
  type Match[IfLT <: Up, IfEQ <: Up, IfGT <: Up, Up] = IfGT
}
sealed trait LT extends Comparison {
  type Match[IfLT <: Up, IfEQ <: Up, IfGT <: Up, Up] = IfLT
}
sealed trait EQ extends Comparison {
  type Match[IfLT <: Up, IfEQ <: Up, IfGT <: Up, Up] = IfEQ
}
 
/**
 * Fold
 */
sealed trait Fold[-Elem, Value] {
  type Apply[E <: Elem, V <: Value] <: Value
}
 
sealed trait IdFold[Elem, Value] extends Fold[Elem, Value] {
  type Apply[E <: Elem, V <: Value] = V
}
 
 
/* value level arith */
object ValueLevel {
  def list(i:Int) = (i to i by -1).toList
 
  //like Succ[N]
  def succ(n:Int) = n+1
 
  //like Add[A<:Nat, B<:Nat]
  def add(a:Int, b:Int) = list(a).fold(b){ (i, acc) => succ(acc) }
 
  def mult(a:Int, b:Int) = list(a).fold(0){ (i, acc) => add(acc, b) }
 
  def exp(a:Int, b:Int) = list(b).fold(1) { (i, acc) => mult(acc, a)}
 
  def fact(a:Int) = list(a).fold(1){ (i, acc) => mult(i, acc)}
 
  def mod(a:Int, b:Int) =  list(a).fold(0) { (i, acc) => if (acc+1 == b) 0 else acc+1 }
}
 
 
/**
 * Nat
 */
sealed trait Nat {
  type Match[ NonZero[N <: Nat] <: Up, IfZero <: Up, Up ] <: Up
 
  type Compare[N <: Nat] <: Comparison
 
  type FoldR[Init <: Type, Type, F <: Fold[Nat, Type] ] <: Type
  type FoldL[Init <: Type, Type, F <: Fold[Nat, Type] ] <: Type
}
sealed trait _0 extends Nat {
  type Match[ NonZero[N <: Nat] <: Up, IfZero <: Up, Up ] = IfZero
 
  type Compare[N <: Nat] = N#Match[ConstLT, EQ, Comparison]
  type ConstLT[A] = LT
 
  type FoldR[Init <: Type, Type, F <: Fold[Nat, Type]] = Init
  type FoldL[Init <: Type, Type, F <: Fold[Nat, Type]] = Init
}
sealed trait Succ[N <: Nat] extends Nat {
  type Match[ NonZero[N <: Nat] <: Up, IfZero <: Up, Up ] = NonZero[N]
 
  //will compare O-1 to N 
  //since we're defining Succ[N], we are at N+1
  // so we will compare both preceeding naturals
  // 3 compare 4
  // = 2 compare 3
  // = 1 compare 2
  // = 0 compare 1
  // = LT
  type Compare[O <: Nat] = O#Match[ N#Compare, GT, Comparison ] 
 
  type FoldR[Init <: Type, Type, F <: Fold[Nat, Type]] =  F#Apply[Succ[N], N#FoldR[Init, Type, F]]
  type FoldL[Init <: Type, Type, F <: Fold[Nat, Type]] =  N#FoldL[F#Apply[Succ[N], Type], Type, F]
}
 
 
object Nat {
  type _1  = Succ[_0]
  type _2  = Succ[_1]
  type _3  = Succ[_2]
  type _4  = Succ[_3]
  type _5  = Succ[_4]
  type _6  = Succ[_5]
  type _7  = Succ[_6]
  type _8  = Succ[_7]
  type _9  = Succ[_8]
  type _10 = Succ[_9]
  
  type ConstFalse[A] = False
  type is0[A <: Nat] = A#Match[ConstFalse, True, Bool]
 
  type F1 =  _0#FoldR[Int, AnyVal, Fold[Nat, AnyVal]]
  implicitly[F1 =:= Int]
  type F2 =  _1#FoldR[Int, AnyVal, IdFold[Nat, AnyVal]]
  implicitly[F2 =:= Int]
 
  type Add[A <: Nat, B <: Nat] = A#FoldR[B, Nat, Inc]
  type Inc = Fold[Nat, Nat] {
    type Apply[N <: Nat, Acc <: Nat] = Succ[Acc]
  }
 
  type Mult[A <: Nat, B <: Nat] = A#FoldR[_0, Nat, Sum[B]]
  type Sum[By <: Nat] = Fold[Nat, Nat] {
    type Apply[N <: Nat, Acc <: Nat] = Add[By, Acc]
  }
 
  type Fact[A <: Nat] = A#FoldL[_1, Nat, Prod]
  type Prod = Fold[Nat, Nat] {
    type Apply[N <: Nat, Acc <: Nat] = Mult[N, Acc]
  }
 
  type Exp[A <: Nat, B <: Nat] = B#FoldR[_1, Nat, ExpFold[A]]
  type ExpFold[By <: Nat] = Fold[Nat, Nat] {
    type Apply[N <: Nat, Acc <: Nat] = Mult[By, Acc]
  }
 
  type Mod[A <: Nat, B <: Nat] = A#FoldR[_0, Nat, ModFold[B]]
  type ModFold[By <: Nat] = Fold[Nat, Nat] {
    type Wrap[Acc <: Nat] = By#Compare[Acc]#eq
    type Apply[N <: Nat, Acc <: Nat] = Wrap[Succ[Acc]]#If[_0, Succ[Acc], Nat]
  }
 
  //copied from Shapeless ^^
  //https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/nat.scala#L235
  trait ToInt[N <: Nat] {
    def apply() : Int
  }
 
  object ToInt {
 
    implicit val toInt0 = new ToInt[_0] {
      def apply() = 0 
    }
    implicit def toIntSucc[N <: Nat](implicit toIntN : ToInt[N]) = new ToInt[Succ[N]] {
      def apply() = toIntN()+1
    }
  }
  //dump into value level
  def toInt[N <: Nat](implicit r: ToInt[N]) = r.apply();
 
  //arith equality
  type ===[A <: Nat, B <: Nat] = A#Compare[B]#eq
 
  //Square
  type Sq[N <: Nat] = Exp[N, _2]
}
 
//because Nat has some limit ... compilation time and Stack size
//Digit
sealed trait Digit {
  type Match[IfOne <: Up, IfZero <: Up, Up] <: Up
  type Compare[D <: Digit] <: Comparison
}
sealed trait Zero extends Digit {
  type Match[IfOne <: Up, IfZero <: Up, Up] = IfZero
  type Compare[D <: Digit] = D#Match[LT, EQ, Comparison]
}
sealed trait One extends Digit {
  type Match[IfOne <: Up, IfZero <: Up, Up] = IfOne
  type Compare[D <: Digit] = D#Match[EQ, GT, Comparison]
}
 
object Digit {
  type is0[D <: Digit] = D#Match[False, True, Bool]
 
  implicitly[is0[Zero] =:= True]
  implicitly[One#Compare[Zero] =:= GT]
}
//type level heterogeneous list with element types constrained to be Digits
sealed trait Dense {
  type digit <: Digit
  type tail <: Dense
 
  type Inc <: Dense
  type Dec <: Dense
  type Add[b <: Dense] <: Dense
  type ShiftR <: Dense
  type ShiftL <: Dense

  type Mult[b <: Dense] <: Dense
  type ReceiveMult[shifted <: Dense, acc <: Dense] <: Dense
 
  type Match[ NonNil <: Up, IsNil <: Up, Up]  <: Up
  type Compare[B <: Dense] = CompareC[B, EQ]
  type CompareC[B <: Dense, Carry <: Comparison] <: Comparison
}
object Dense {
  type ::[d <:Digit, T <: Dense] = DCons[d, T]
  
  sealed trait DCons[d <: Digit, T <: Dense] extends Dense {
    type digit = d
   
    type tail = T
    type Inc = digit#Match[Zero :: T#Inc, One :: T, Dense]
    type Dec = digit#Match[ tail#Match[ Zero :: tail, DNil, Dense ], One :: tail#Dec, Dense ]
    
    type Add[b <: Dense] =
      b#Match[
        AddNZ[b],    //add a non zero (read non-empty)
        d :: T, //return simply "this" because b is void (nil)
        Dense]
    type AddNZ[b <: Dense] =
      d#Match[
        Add1[b], // add 1 to b because "d" is One
        b#digit :: tail#Add[b#tail], //if "d" is Zero then we keep "b" and we add the tails together
        Dense]
    type Add1[b <: Dense] =
      b#digit#Match[
        Zero :: tail#Add[b#tail]#Inc, // add 1 to 1 so we can shift left the addition of the tails ... to chich we add 1 (Inc)
        d :: tail#Add[b#tail], // si b est Zero alors on garde "d" et on ajoute le reste
        Dense]
    
    type ShiftR = tail
    type ShiftL = Zero :: d :: T
    type Mult[b <: Dense] = b#Compare[d :: T]#Match[ b#ReceiveMult[ d :: T, DNil] , ReceiveMult[b, DNil] , ReceiveMult[b, DNil], Dense ]
    /*
     * Binary Mult
     *     0-2-4-8
     * x = 1 0 0 1 = 9
     * y = 1 1 1 1 = 15
     * x*y = (1 * y)  + (0 * 2y) + (0 * 3y) + (1 * 4y) 
     *     = (1 * 15) + (0 * 30) + (0 * 60) + (1 * 120) 
     *     = 135
     *
     * So that:
     * ShiftL => mult by 2
     * acc => if digit is One then shifted is accumulated 
     */
    type ReceiveMult[shifted <: Dense, acc <: Dense] =  Hack[tail#ReceiveMult[shifted#ShiftL, digit#Match[acc#Add[shifted], acc, Dense]]]
    // prevents a cyclic reference when doing: type A = _3#Mult[_3].
    type Hack[D <: Dense] = D  
   
    type Match[ NonNil <: Up, IsNil <: Up, Up]  = NonNil
   
    type CompareC[B <: Dense, Carry <: Comparison] = B#Match[ CompareNZ[B, Carry], GT, Comparison]
    type CompareNZ[B <: Dense, C <: Comparison] = tail#CompareC[ B#tail, Carry[digit#Compare[B#digit], C] ] //on compare les tails et conservant la "comparaison" en cours (accumulateur)
    type Carry[New <: Comparison, C <: Comparison] = New#Match[ LT, C, GT, Comparison] //plus on avance dans la "liste" plus le bit a de l'importance et donc prend la précédence dans la Comparaison
  }
  sealed trait DNil extends Dense {
    type digit = Nothing
    type tail = Nothing
   
    type Inc = One :: DNil
    type Dec = Nothing
    type Add[b <: Dense] = b
    type ShiftR = DNil
    type ShiftL = DNil

    type Mult[b <: Dense] = DNil
    type ReceiveMult[shifted <: Dense, acc <: Dense] = acc

    type Match[ NonNil <: Up, IsNil <: Up, Up]  = IsNil
    type CompareC[B <: Dense, C <: Comparison] = B#Match[ LT, C, Comparison]
  }
 
  type _D0 = Zero :: DNil
  type _D1 = One :: DNil
  type _D2 = Zero :: One :: DNil
  type _D3 = One :: One :: DNil
  type _D4 = Zero :: Zero :: One :: DNil
  type _D5 = One :: Zero :: One :: DNil
 
  def dToInt[D <: Dense](implicit r:DRep[D]): Int = r.value
  class DRep[D <: Dense](val value:Int) {}
  implicit def dnilToRep = new DRep[DNil](0)
  implicit def dcons0ToRep[D <: Dense](implicit tailRep: DRep[D]): DRep[DCons[Zero, D]] = new DRep(tailRep.value * 2)
  implicit def dcons1ToRep[D <: Dense](implicit tailRep: DRep[D]): DRep[DCons[One, D]]  = new DRep(tailRep.value * 2 + 1)
}
 
 
 
object Test extends Application {
  import Bool._
  import Nat._
  import Dense._
  println( toBoolean[ Sq[_9] === Add[_1, Mult[_8, _10]]] )
  println( toInt[ _9] )
  println( toInt[ Sq[_4]] )
  println( dToInt[ _D5 ] )
  println( dToInt[ _D5#Inc ] == 6 )
  println( dToInt[ _D5#Inc#Add[_D4] ] == 10 )
  println( dToInt[ _D5#Mult[_D3]] == 15 )
  println( dToInt[ _D5#Dec] == 4 )
  //println( toInt[Add[_1, Mult[_8, _10]]]  )
  //println( toBoolean[ Eq[ Sq[Sq[_9]], Sq[Add[_1,Mult[_8,_10]]] ] ] )
  //assert( toBoolean[ Mod[ Exp[_9,_4], _6] === _3 ] )
  //println(toInt[ Mod[ Sq[_9], _6] ] == 81 % 6)
}