This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Reversed matching on Lists

4 replies
Ricky Clarkson
Joined: 2008-12-19,
User offline. Last seen 3 years 2 weeks ago.
Hi,

[ summary: I want something like 'case rest >> x >> y >> z', which means the same as 'case z :: y :: x :: rest'.  I don't mind whether it's for scala.List or some other type ]

The 29 lines of code at the end of this email implement the first language from Types and Programming Languages, by Benjamin C. Pierce, but as postfix.  You're welcome to try it out.  Some sample input and instructions are included too.

In the interpreted code, one might have:

O succ isZero O isZero

which results in a stack containing false, true, because the successor of O is not zero, but O is zero.

So whenever isZero is processed we're interested in preserving the rest of the stack before the head, but testing whether the head is zero.  In Scala:

case "isZero" => stack match { case O :: rest => True :: rest
                               case _ :: rest => False :: rest }

The cases and their results are written in exactly the opposite order to the interpreted code.
  It would be great if I could write:

case "isZero" => stack match { case rest >> O => rest >> True
                               case rest >> _ => rest >> False }

This at least might make my mistake in the order for 'if' harder to make!  If anyone has already implemented this somewhere, please let me see it!

Anyway, to run the interpreter, save the following code as xyz.scala, and run:
scala xyz.scala
(it's a script, so you don't use scalac on it).
When the prompt appears, here are some example expressions:

O succ
O isZero
O succ pred isZero
true false true if

And the code:

sealed trait Term
case object True extends Term
case object False extends Term
case object O extends Term
case class Succ(t: Term) extends Term

def parseTerm(s: String, stack: List[Term]): List[Term] = s match {
 case "true" => True :: stack
 case "false" => False :: stack
 case "O" => O :: stack
 case "succ" => stack match { case t :: rest => Succ(t) :: rest
                              case _ => throw null }
 case "pred" => stack match { case O :: rest => O :: rest
                              case Succ(t) :: rest => t :: rest
                              case _ => throw null }
 case "if" => stack match { case True :: otherwise :: then :: rest => then :: rest
                            case False :: otherwise :: then :: rest => otherwise :: rest
                            case _ => throw null }
 case "isZero" => stack match { case O :: rest => True :: rest
                                case _ :: rest => False :: rest
                                case _ => throw null }
}

println
print("> ")
import java.io.{BufferedReader, InputStreamReader}
val in = new BufferedReader(new InputStreamReader(System.in, "UTF-8"))
val line = in.readLine
println(line.split(" ").foldLeft(Nil : List[Term])((stack, token) => parseTerm(token, stack)))
ewilligers
Joined: 2008-08-20,
User offline. Last seen 3 years 17 weeks ago.
Re: Reversed matching on Lists

Use the attached, with

def makeReverseList[A](xs: List[A]): ReverseList[A] = xs match {
case Nil => ReverseNil
case h :: t => makeReverseList(t) >> h
}

println(makeReverseList(line.split(" ").toList).
fold(ReverseNil : ReverseList[Term])((token, stack) =>
parseTerm(token,stack)))

Sebastien Bocq
Joined: 2008-12-18,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Reversed matching on Lists
Hi,

Isn't :: not covariant because it's sole intended use is pattern matching?

Wouldn't it be more convenient to create a BidirList class inheriting from List but maintains two list internally, one in normal order for the head and one in reverse order for the tail (like what is done in the immutable Queue class) and define a '>>' case for that one?

This way BidirList can be used as a regular List - a method like:

def mean(xs: List[Number]) = xs.reduceLeft(_ + _) / xs.length

would work on both.

And if a BidirList is used you can additionally match it against '>>'.

Would something like that work?

- Sebastien

2009/1/13 Eric Willigers <ewilligers [at] gmail [dot] com>
Use the attached, with

def makeReverseList[A](xs: List[A]): ReverseList[A] = xs match {
   case Nil => ReverseNil
   case h :: t => makeReverseList(t) >> h
}

println(makeReverseList(line.split(" ").toList).
 fold(ReverseNil : ReverseList[Term])((token, stack) =>
   parseTerm(token,stack)))




package pkg

sealed abstract class ReverseList[+A] {
   // List method :: currently returns a List, it could return a ::
   def >>[B >: A](x: B): >>[B] = pkg.>>(this, x)

   def isEmpty: Boolean
   def tail: ReverseList[A]
   def head: A

 // based on List's foldLeft -
 def fold[B](z: B)(f: (A, B) => B): B = {

   def loop(acc: B, these: ReverseList[A]): B = these match {
       case ReverseNil => acc
       case tl >> hd => loop(f(hd, acc), tl)
   }

   loop(z, this)
 }
}

final case object ReverseNil extends ReverseList[Nothing] {
   def isEmpty = true
   def tail = throw new NoSuchElementException("tail of empty ReverseList")
   def head = throw new NoSuchElementException("head of empty ReverseList")
}

// :: isn't covariant, it could be
final case class >>[+A](tail: ReverseList[A], head: A) extends ReverseList[A] {
   def isEmpty = false
}



ewilligers
Joined: 2008-08-20,
User offline. Last seen 3 years 17 weeks ago.
Re: Reversed matching on Lists

Sebastien Bocq wrote:
> Wouldn't it be more convenient to create a BidirList class inheriting
> from List but maintains two list internally, one in normal order for the
> head and one in reverse order for the tail (like what is done in the
> immutable Queue class) and define a '>>' case for that one?
>
> This way BidirList can be used as a regular List - a method like:

or we add >> to List using Pimp My Library.

class BidirList[A](list: List[A]) {
def >>[B >: A](x: B): List[B] = x :: list
}

object >> {
def unapply[A](cons: scala.::[A]): Option[(List[A], A)] =
Some((cons.tail, cons.head))
}

implicit def list2BidirList[A](xs: List[A]): BidirList[A] = new
BidirList(xs)

Ricky Clarkson
Joined: 2008-12-19,
User offline. Last seen 3 years 2 weeks ago.
Re: Re: Reversed matching on Lists
Thanks for the excellent responses.

Here's my resultant code after including this.  http://pastebin.com/f10afd6cc

I find it much more readable, especially the case "if" line.  I can't get the order wrong quite as easily now.

2009/1/13 Eric Willigers <ewilligers [at] gmail [dot] com>
Sebastien Bocq wrote:
Wouldn't it be more convenient to create a BidirList class inheriting from List but maintains two list internally, one in normal order for the head and one in reverse order for the tail (like what is done in the immutable Queue class) and define a '>>' case for that one?

This way BidirList can be used as a regular List - a method like:

or we add >> to List using Pimp My Library.



class BidirList[A](list: List[A]) {
   def >>[B >: A](x: B): List[B] = x :: list
}

object >> {
   def unapply[A](cons: scala.::[A]): Option[(List[A], A)] = Some((cons.tail, cons.head))
}

implicit def list2BidirList[A](xs: List[A]): BidirList[A] = new BidirList(xs)


Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland