small puzzle

if the list is already sorted by some ordering: new treeset(yourlist,
yourcomparator)

if it is randomly sorted: new linkedhashset(yourlist)

Am 09.04.2011 12:02, schrieb Tony Morris:
> * Remove duplicate elements from a List.
> * Elements have ordering defined.
> * Do not use updating variables.
> * Maintain original insertion order (though any of the duplicates may be
> removed).
> * It may help to implement additional library support. At your discretion.
>
> sealed trait Ordering
> case object LT extends Ordering
> case object EQ extends Ordering
> case object GT extends Ordering
>
> trait Order[A] {
> def compare(a1: A, a2: A): Ordering
>
> def contramap[B](f: B => A): Order[B] =
> new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
> f(b2))
> }
>
> def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
> error("todo")
>

The list is not sorted.

LinkedHashSet uses variables. It also violates the rules. Elements have
order, not necessarily hash-codes (ignore the fact that Java/Scala
pretends otherwise).

On 09/04/11 20:23, HamsterofDeath wrote:
> if the list is already sorted by some ordering: new treeset(yourlist,
> yourcomparator)
>
> if it is randomly sorted: new linkedhashset(yourlist)
>
>
>
>
>
> Am 09.04.2011 12:02, schrieb Tony Morris:
>> * Remove duplicate elements from a List.
>> * Elements have ordering defined.
>> * Do not use updating variables.
>> * Maintain original insertion order (though any of the duplicates may be
>> removed).
>> * It may help to implement additional library support. At your discretion.
>>
>> sealed trait Ordering
>> case object LT extends Ordering
>> case object EQ extends Ordering
>> case object GT extends Ordering
>>
>> trait Order[A] {
>> def compare(a1: A, a2: A): Ordering
>>
>> def contramap[B](f: B => A): Order[B] =
>> new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
>> f(b2))
>> }
>>
>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
>> error("todo")
>>

so there is a list and i have to a) sort it and b) remove duplicates?

Am 09.04.2011 13:39, schrieb Tony Morris:
> The list is not sorted.
>
> LinkedHashSet uses variables. It also violates the rules. Elements have
> order, not necessarily hash-codes (ignore the fact that Java/Scala
> pretends otherwise).
>
> On 09/04/11 20:23, HamsterofDeath wrote:
>> if the list is already sorted by some ordering: new treeset(yourlist,
>> yourcomparator)
>>
>> if it is randomly sorted: new linkedhashset(yourlist)
>>
>>
>>
>>
>>
>> Am 09.04.2011 12:02, schrieb Tony Morris:
>>> * Remove duplicate elements from a List.
>>> * Elements have ordering defined.
>>> * Do not use updating variables.
>>> * Maintain original insertion order (though any of the duplicates may be
>>> removed).
>>> * It may help to implement additional library support. At your discretion.
>>>
>>> sealed trait Ordering
>>> case object LT extends Ordering
>>> case object EQ extends Ordering
>>> case object GT extends Ordering
>>>
>>> trait Order[A] {
>>> def compare(a1: A, a2: A): Ordering
>>>
>>> def contramap[B](f: B => A): Order[B] =
>>> new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
>>> f(b2))
>>> }
>>>
>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
>>> error("todo")
>>>
>

a) No, the list that is returned must retain original order. b) Yes.

On 09/04/11 21:50, HamsterofDeath wrote:
> so there is a list and i have to a) sort it and b) remove duplicates?
>
> Am 09.04.2011 13:39, schrieb Tony Morris:
>> The list is not sorted.
>>
>> LinkedHashSet uses variables. It also violates the rules. Elements have
>> order, not necessarily hash-codes (ignore the fact that Java/Scala
>> pretends otherwise).
>>
>> On 09/04/11 20:23, HamsterofDeath wrote:
>>> if the list is already sorted by some ordering: new treeset(yourlist,
>>> yourcomparator)
>>>
>>> if it is randomly sorted: new linkedhashset(yourlist)
>>>
>>>
>>>
>>>
>>>
>>> Am 09.04.2011 12:02, schrieb Tony Morris:
>>>> * Remove duplicate elements from a List.
>>>> * Elements have ordering defined.
>>>> * Do not use updating variables.
>>>> * Maintain original insertion order (though any of the duplicates may be
>>>> removed).
>>>> * It may help to implement additional library support. At your discretion.
>>>>
>>>> sealed trait Ordering
>>>> case object LT extends Ordering
>>>> case object EQ extends Ordering
>>>> case object GT extends Ordering
>>>>
>>>> trait Order[A] {
>>>> def compare(a1: A, a2: A): Ordering
>>>>
>>>> def contramap[B](f: B => A): Order[B] =
>>>> new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
>>>> f(b2))
>>>> }
>>>>
>>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
>>>> error("todo")
>>>>

By variables you mean mutable state or any passed around state?

On Sat, Apr 9, 2011 at 1:59 PM, Tony Morris <tonymorris@gmail.com> wrote:

a) No, the list that is returned must retain original order. b) Yes.


On 09/04/11 21:50, HamsterofDeath wrote:
> so there is a list and i have to a) sort it and b) remove duplicates?
>
> Am 09.04.2011 13:39, schrieb Tony Morris:
>> The list is not sorted.
>>
>> LinkedHashSet uses variables. It also violates the rules. Elements have
>> order, not necessarily hash-codes (ignore the fact that Java/Scala
>> pretends otherwise).
>>
>> On 09/04/11 20:23, HamsterofDeath wrote:
>>> if the list is already sorted by some ordering: new treeset(yourlist,
>>> yourcomparator)
>>>
>>> if it is randomly sorted: new linkedhashset(yourlist)
>>>
>>>
>>>
>>>
>>>
>>> Am 09.04.2011 12:02, schrieb Tony Morris:
>>>> * Remove duplicate elements from a List.
>>>> * Elements have ordering defined.
>>>> * Do not use updating variables.
>>>> * Maintain original insertion order (though any of the duplicates may be
>>>> removed).
>>>> * It may help to implement additional library support. At your discretion.
>>>>
>>>> sealed trait Ordering
>>>> case object LT extends Ordering
>>>> case object EQ extends Ordering
>>>> case object GT extends Ordering
>>>>
>>>> trait Order[A] {
>>>>   def compare(a1: A, a2: A): Ordering
>>>>
>>>>   def contramap[B](f: B => A): Order[B] =
>>>>     new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
>>>> f(b2))
>>>> }
>>>>
>>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
>>>> error("todo")
>>>>


--
Tony Morris
http://tmorris.net/

--
www.sadekdrobi.com
ʎdoɹʇuǝ

This seems too easy unless solutions need to run in O(n log n).  (I assume we have an order so that O(n log n) is possible? Otherwise you only need to test equality.)
  --Rex

On Sat, Apr 9, 2011 at 6:02 AM, Tony Morris <tonymorris@gmail.com> wrote:

* Remove duplicate elements from a List.
* Elements have ordering defined.
* Do not use updating variables.
* Maintain original insertion order (though any of the duplicates may be
removed).
* It may help to implement additional library support. At your discretion.

sealed trait Ordering
case object LT extends Ordering
case object EQ extends Ordering
case object GT extends Ordering

trait Order[A] {
 def compare(a1: A, a2: A): Ordering

 def contramap[B](f: B => A): Order[B] =
   new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
f(b2))
}

def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
error("todo")

--
Tony Morris
http://tmorris.net/

this?

(Nil /: originalList)(acc, e => if (acc.contains(e) acc else e :: acc)).reverse



i am confused about that implicit order thingy.

Am 09.04.2011 14:03, schrieb Sadek Drobi:

BANLkTik67oKX0v9R7RCy4pt-pR08OuttKA [at] mail [dot] gmail [dot] com" type="cite"> By variables you mean mutable state or any passed around state?

On Sat, Apr 9, 2011 at 1:59 PM, Tony Morris <tonymorris [at] gmail [dot] com" rel="nofollow">tonymorris@gmail.com> wrote:

a) No, the list that is returned must retain original order. b) Yes.


On 09/04/11 21:50, HamsterofDeath wrote:
> so there is a list and i have to a) sort it and b) remove duplicates?
>
> Am 09.04.2011 13:39, schrieb Tony Morris:
>> The list is not sorted.
>>
>> LinkedHashSet uses variables. It also violates the rules. Elements have
>> order, not necessarily hash-codes (ignore the fact that Java/Scala
>> pretends otherwise).
>>
>> On 09/04/11 20:23, HamsterofDeath wrote:
>>> if the list is already sorted by some ordering: new treeset(yourlist,
>>> yourcomparator)
>>>
>>> if it is randomly sorted: new linkedhashset(yourlist)
>>>
>>>
>>>
>>>
>>>
>>> Am 09.04.2011 12:02, schrieb Tony Morris:
>>>> * Remove duplicate elements from a List.
>>>> * Elements have ordering defined.
>>>> * Do not use updating variables.
>>>> * Maintain original insertion order (though any of the duplicates may be
>>>> removed).
>>>> * It may help to implement additional library support. At your discretion.
>>>>
>>>> sealed trait Ordering
>>>> case object LT extends Ordering
>>>> case object EQ extends Ordering
>>>> case object GT extends Ordering
>>>>
>>>> trait Order[A] {
>>>>   def compare(a1: A, a2: A): Ordering
>>>>
>>>>   def contramap[B](f: B => A): Order[B] =
>>>>     new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
>>>> f(b2))
>>>> }
>>>>
>>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
>>>> error("todo")
>>>>


--
Tony Morris
http://tmorris.net/

--
www.sadekdrobi.com
ʎdoɹʇuǝ

Bit slow innit?

Not sure how to make the order thingy any clearer.

On 09/04/2011 10:28 PM, "HamsterofDeath" <h-star@gmx.de> wrote:
> this?
>
> (Nil /: originalList)(acc, e => if (acc.contains(e) acc else e ::
> acc)).reverse
>
>
>
> i am confused about that implicit order thingy.
>
> Am 09.04.2011 14:03, schrieb Sadek Drobi:
>> By variables you mean mutable state or any passed around state?
>>
>> On Sat, Apr 9, 2011 at 1:59 PM, Tony Morris <tonymorris@gmail.com
>> <mailto:tonymorris@gmail.com>> wrote:
>>
>> a) No, the list that is returned must retain original order. b) Yes.
>>
>>
>> On 09/04/11 21:50, HamsterofDeath wrote:
>> > so there is a list and i have to a) sort it and b) remove
>> duplicates?
>> >
>> > Am 09.04.2011 13:39, schrieb Tony Morris:
>> >> The list is not sorted.
>> >>
>> >> LinkedHashSet uses variables. It also violates the rules.
>> Elements have
>> >> order, not necessarily hash-codes (ignore the fact that Java/Scala
>> >> pretends otherwise).
>> >>
>> >> On 09/04/11 20:23, HamsterofDeath wrote:
>> >>> if the list is already sorted by some ordering: new
>> treeset(yourlist,
>> >>> yourcomparator)
>> >>>
>> >>> if it is randomly sorted: new linkedhashset(yourlist)
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> Am 09.04.2011 12:02, schrieb Tony Morris:
>> >>>> * Remove duplicate elements from a List.
>> >>>> * Elements have ordering defined.
>> >>>> * Do not use updating variables.
>> >>>> * Maintain original insertion order (though any of the
>> duplicates may be
>> >>>> removed).
>> >>>> * It may help to implement additional library support. At
>> your discretion.
>> >>>>
>> >>>> sealed trait Ordering
>> >>>> case object LT extends Ordering
>> >>>> case object EQ extends Ordering
>> >>>> case object GT extends Ordering
>> >>>>
>> >>>> trait Order[A] {
>> >>>> def compare(a1: A, a2: A): Ordering
>> >>>>
>> >>>> def contramap[B](f: B => A): Order[B] =
>> >>>> new Order[B] { def compare(b1: B, b2: B) =
>> Order.this.compare(f(b1),
>> >>>> f(b2))
>> >>>> }
>> >>>>
>> >>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]):
>> List[A] =
>> >>>> error("todo")
>> >>>>
>>
>>
>> --
>> Tony Morris
>> http://tmorris.net/
>>
>>
>>
>>
>>
>> --
>> www.sadekdrobi.com <http://www.sadekdrobi.com>
>> ʎdoɹʇuǝ
>

yes it's slow, but you didn't request a fast solution ;). if you did, i would use a purely functional linkedhashset and simply assume such a collection exists.

what to i need the order parameter for? i mean, i am supposed to use the ordering of the given list. is it a helper that tells me the original ordering of 2 elements in constant time?

Am 09.04.2011 15:34, schrieb Tony Morris:

BANLkTim9EnLsNimzWZkxP0Taao7msbZy+g [at] mail [dot] gmail [dot] com" type="cite">

Bit slow innit?

Not sure how to make the order thingy any clearer.

On 09/04/2011 10:28 PM, "HamsterofDeath" <h-star [at] gmx [dot] de" rel="nofollow">h-star@gmx.de> wrote:
> this?
>
> (Nil /: originalList)(acc, e => if (acc.contains(e) acc else e ::
> acc)).reverse
>
>
>
> i am confused about that implicit order thingy.
>
> Am 09.04.2011 14:03, schrieb Sadek Drobi:
>> By variables you mean mutable state or any passed around state?
>>
>> On Sat, Apr 9, 2011 at 1:59 PM, Tony Morris <tonymorris [at] gmail [dot] com" rel="nofollow">tonymorris@gmail.com
>> <mailto:tonymorris [at] gmail [dot] com" rel="nofollow">tonymorris@gmail.com>> wrote:
>>
>> a) No, the list that is returned must retain original order. b) Yes.
>>
>>
>> On 09/04/11 21:50, HamsterofDeath wrote:
>> > so there is a list and i have to a) sort it and b) remove
>> duplicates?
>> >
>> > Am 09.04.2011 13:39, schrieb Tony Morris:
>> >> The list is not sorted.
>> >>
>> >> LinkedHashSet uses variables. It also violates the rules.
>> Elements have
>> >> order, not necessarily hash-codes (ignore the fact that Java/Scala
>> >> pretends otherwise).
>> >>
>> >> On 09/04/11 20:23, HamsterofDeath wrote:
>> >>> if the list is already sorted by some ordering: new
>> treeset(yourlist,
>> >>> yourcomparator)
>> >>>
>> >>> if it is randomly sorted: new linkedhashset(yourlist)
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> Am 09.04.2011 12:02, schrieb Tony Morris:
>> >>>> * Remove duplicate elements from a List.
>> >>>> * Elements have ordering defined.
>> >>>> * Do not use updating variables.
>> >>>> * Maintain original insertion order (though any of the
>> duplicates may be
>> >>>> removed).
>> >>>> * It may help to implement additional library support. At
>> your discretion.
>> >>>>
>> >>>> sealed trait Ordering
>> >>>> case object LT extends Ordering
>> >>>> case object EQ extends Ordering
>> >>>> case object GT extends Ordering
>> >>>>
>> >>>> trait Order[A] {
>> >>>> def compare(a1: A, a2: A): Ordering
>> >>>>
>> >>>> def contramap[B](f: B => A): Order[B] =
>> >>>> new Order[B] { def compare(b1: B, b2: B) =
>> Order.this.compare(f(b1),
>> >>>> f(b2))
>> >>>> }
>> >>>>
>> >>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]):
>> List[A] =
>> >>>> error("todo")
>> >>>>
>>
>>
>> --
>> Tony Morris
>> http://tmorris.net/
>>
>>
>>
>>
>>
>> --
>> www.sadekdrobi.com <http://www.sadekdrobi.com>
>> ʎdoɹʇuǝ
>

Writing from phone. But an outline of a solution would be to iterate over element of the input list accumulating a filter. The current element is either in the filter and filtered out or not and accumulated into the result. Use ordering to keep the filter sorted enabling fast filter checking. The filter can be built via an ordered tree. Will try to hack something out later.

Thoughts?

--
Jim Powers

On Apr 9, 2011 9:54 AM, "HamsterofDeath" <h-star@gmx.de> wrote:
> yes it's slow, but you didn't request a fast solution ;). if you did, i
> would use a purely functional linkedhashset and simply assume such a
> collection exists.
>
> what to i need the order parameter for? i mean, i am supposed to use the
> ordering of the given list. is it a helper that tells me the original
> ordering of 2 elements in constant time?
>
> Am 09.04.2011 15:34, schrieb Tony Morris:
>>
>> Bit slow innit?
>>
>> Not sure how to make the order thingy any clearer.
>>
>> On 09/04/2011 10:28 PM, "HamsterofDeath" <h-star@gmx.de
>> <mailto:h-star@gmx.de>> wrote:
>> > this?
>> >
>> > (Nil /: originalList)(acc, e => if (acc.contains(e) acc else e ::
>> > acc)).reverse
>> >
>> >
>> >
>> > i am confused about that implicit order thingy.
>> >
>> > Am 09.04.2011 14:03, schrieb Sadek Drobi:
>> >> By variables you mean mutable state or any passed around state?
>> >>
>> >> On Sat, Apr 9, 2011 at 1:59 PM, Tony Morris <tonymorris@gmail.com
>> <mailto:tonymorris@gmail.com>
>> >> <mailto:tonymorris@gmail.com <mailto:tonymorris@gmail.com>>> wrote:
>> >>
>> >> a) No, the list that is returned must retain original order. b) Yes.
>> >>
>> >>
>> >> On 09/04/11 21:50, HamsterofDeath wrote:
>> >> > so there is a list and i have to a) sort it and b) remove
>> >> duplicates?
>> >> >
>> >> > Am 09.04.2011 13:39, schrieb Tony Morris:
>> >> >> The list is not sorted.
>> >> >>
>> >> >> LinkedHashSet uses variables. It also violates the rules.
>> >> Elements have
>> >> >> order, not necessarily hash-codes (ignore the fact that Java/Scala
>> >> >> pretends otherwise).
>> >> >>
>> >> >> On 09/04/11 20:23, HamsterofDeath wrote:
>> >> >>> if the list is already sorted by some ordering: new
>> >> treeset(yourlist,
>> >> >>> yourcomparator)
>> >> >>>
>> >> >>> if it is randomly sorted: new linkedhashset(yourlist)
>> >> >>>
>> >> >>>
>> >> >>>
>> >> >>>
>> >> >>>
>> >> >>> Am 09.04.2011 12:02, schrieb Tony Morris:
>> >> >>>> * Remove duplicate elements from a List.
>> >> >>>> * Elements have ordering defined.
>> >> >>>> * Do not use updating variables.
>> >> >>>> * Maintain original insertion order (though any of the
>> >> duplicates may be
>> >> >>>> removed).
>> >> >>>> * It may help to implement additional library support. At
>> >> your discretion.
>> >> >>>>
>> >> >>>> sealed trait Ordering
>> >> >>>> case object LT extends Ordering
>> >> >>>> case object EQ extends Ordering
>> >> >>>> case object GT extends Ordering
>> >> >>>>
>> >> >>>> trait Order[A] {
>> >> >>>> def compare(a1: A, a2: A): Ordering
>> >> >>>>
>> >> >>>> def contramap[B](f: B => A): Order[B] =
>> >> >>>> new Order[B] { def compare(b1: B, b2: B) =
>> >> Order.this.compare(f(b1),
>> >> >>>> f(b2))
>> >> >>>> }
>> >> >>>>
>> >> >>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]):
>> >> List[A] =
>> >> >>>> error("todo")
>> >> >>>>
>> >>
>> >>
>> >> --
>> >> Tony Morris
>> >> http://tmorris.net/
>> >>
>> >>
>> >>
>> >>
>> >>
>> >> --
>> >> www.sadekdrobi.com <http://www.sadekdrobi.com>
>> <http://www.sadekdrobi.com>
>> >> ʎdoɹʇuǝ
>> >
>

On Sat, Apr 9, 2011 at 10:05 AM, Jim Powers <jim@casapowers.com> wrote:

Writing from phone. But an outline of a solution would be to iterate over element of the input list accumulating a filter. The current element is either in the filter and filtered out or not and accumulated into the result. Use ordering to keep the filter sorted enabling fast filter checking. The filter can be built via an ordered tree. Will try to hack something out later.

Thoughts

Trees are a pain.  Mergesort is easy.

  --Rex

I think this will do the trick:
object Test {  import scala.collection.immutable.SortedSet   import scala.math.Ordering  def removeDuplicates[A](a: List[A])(implicit ord: Ordering[A]):List[A] = {     def rdInt:(List[A],SortedSet[A],List[A]) => List[A] = {      case (Nil,filter:SortedSet[A],result:List[A]) => result.reverse       case (x :: xs,filter:SortedSet[A],result:List[A]) =>         if (filter.contains(x)) rdInt(xs,filter,result)         else rdInt(xs,filter + x,x :: result)    }     rdInt(a,SortedSet[A](),Nil)  }}
Sample run:
Test.removeDuplicates(List(1,8,7,4,3,5,7,8,3,2,2,1,0,9,4))res2: List[Int] = List(1, 8, 7, 4, 3, 5, 2, 0, 9)
Notes:1. I only did a casual inspection of SortedSet, I certainly didn't find any obvious mutable variables.  That said, the above approach could simply utilize a version of 'SortableSet' that met the rules of the game. 2. Using scala.math.Ordering as s substitution to Tony's helper class.  The only thing stopping me from using Tony's class the the time I have to write a solution to this puzzle (which is quite constrained as multiple of my children are demanding my attention ;-) ).  It seems obvious to me that a solution to Tony's puzzle should be easily implemented with his helper class.
Hoping I didn't miss anything obvious.
On Sat, Apr 9, 2011 at 10:25 AM, Rex Kerr <ichoran@gmail.com> wrote:

On Sat, Apr 9, 2011 at 10:05 AM, Jim Powers <jim@casapowers.com> wrote:

Writing from phone. But an outline of a solution would be to iterate over element of the input list accumulating a filter. The current element is either in the filter and filtered out or not and accumulated into the result. Use ordering to keep the filter sorted enabling fast filter checking. The filter can be built via an ordered tree. Will try to hack something out later.

Thoughts

Trees are a pain.  Mergesort is easy.

  --Rex

--
Jim Powers

Using folds:
object Test1 {  import scala.collection.immutable.SortedSet   import scala.math.Ordering  def removeDuplicates[A](a: List[A])(implicit ord: Ordering[A]):List[A] = {     (a.foldLeft((SortedSet[A](),List[A]())) {      case ((filter,result),x) =>          if (filter.contains(x)) (filter,result)        else (filter + x,x :: result)     })._2.reverse  }}

On Sat, Apr 9, 2011 at 11:44 AM, Jim Powers <jim@casapowers.com> wrote:

I think this will do the trick:
object Test {  import scala.collection.immutable.SortedSet   import scala.math.Ordering  def removeDuplicates[A](a: List[A])(implicit ord: Ordering[A]):List[A] = {     def rdInt:(List[A],SortedSet[A],List[A]) => List[A] = {      case (Nil,filter:SortedSet[A],result:List[A]) => result.reverse       case (x :: xs,filter:SortedSet[A],result:List[A]) =>         if (filter.contains(x)) rdInt(xs,filter,result)         else rdInt(xs,filter + x,x :: result)    }     rdInt(a,SortedSet[A](),Nil)  }}
Sample run:
Test.removeDuplicates(List(1,8,7,4,3,5,7,8,3,2,2,1,0,9,4))res2: List[Int] = List(1, 8, 7, 4, 3, 5, 2, 0, 9)
Notes:1. I only did a casual inspection of SortedSet, I certainly didn't find any obvious mutable variables.  That said, the above approach could simply utilize a version of 'SortableSet' that met the rules of the game. 2. Using scala.math.Ordering as s substitution to Tony's helper class.  The only thing stopping me from using Tony's class the the time I have to write a solution to this puzzle (which is quite constrained as multiple of my children are demanding my attention ;-) ).  It seems obvious to me that a solution to Tony's puzzle should be easily implemented with his helper class.
Hoping I didn't miss anything obvious.
On Sat, Apr 9, 2011 at 10:25 AM, Rex Kerr <ichoran@gmail.com> wrote:

On Sat, Apr 9, 2011 at 10:05 AM, Jim Powers <jim@casapowers.com> wrote:

Writing from phone. But an outline of a solution would be to iterate over element of the input list accumulating a filter. The current element is either in the filter and filtered out or not and accumulated into the result. Use ordering to keep the filter sorted enabling fast filter checking. The filter can be built via an ordered tree. Will try to hack something out later.

Thoughts

Trees are a pain.  Mergesort is easy.

  --Rex

--
Jim Powers

--
Jim Powers

Attached (spoiler alert, if Jim's method doesn't count already) is a solution that doesn't use a second collection, just List.  (Well, and Option.)  It's more complex than it needs to be via specifications, since it returns the _first_ item out of the duplicates, not any item, and it uses the Ordering trait as given.

Thanks to Tony for the "puzzle"!

  --Rex

On Sat, Apr 9, 2011 at 6:02 AM, Tony Morris <tonymorris@gmail.com> wrote:

* Remove duplicate elements from a List.
* Elements have ordering defined.
* Do not use updating variables.
* Maintain original insertion order (though any of the duplicates may be
removed).
* It may help to implement additional library support. At your discretion.

sealed trait Ordering
case object LT extends Ordering
case object EQ extends Ordering
case object GT extends Ordering

trait Order[A] {
 def compare(a1: A, a2: A): Ordering

 def contramap[B](f: B => A): Order[B] =
   new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
f(b2))
}

def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
error("todo")

--
Tony Morris
http://tmorris.net/

is my solution correct?

Am 09.04.2011 15:34, schrieb Tony Morris:

BANLkTim9EnLsNimzWZkxP0Taao7msbZy+g [at] mail [dot] gmail [dot] com" type="cite">

Bit slow innit?

Not sure how to make the order thingy any clearer.

On 09/04/2011 10:28 PM, "HamsterofDeath" <h-star [at] gmx [dot] de" rel="nofollow">h-star@gmx.de> wrote:
> this?
>
> (Nil /: originalList)(acc, e => if (acc.contains(e) acc else e ::
> acc)).reverse
>
>
>
> i am confused about that implicit order thingy.
>
> Am 09.04.2011 14:03, schrieb Sadek Drobi:
>> By variables you mean mutable state or any passed around state?
>>
>> On Sat, Apr 9, 2011 at 1:59 PM, Tony Morris <tonymorris [at] gmail [dot] com" rel="nofollow">tonymorris@gmail.com
>> <mailto:tonymorris [at] gmail [dot] com" rel="nofollow">tonymorris@gmail.com>> wrote:
>>
>> a) No, the list that is returned must retain original order. b) Yes.
>>
>>
>> On 09/04/11 21:50, HamsterofDeath wrote:
>> > so there is a list and i have to a) sort it and b) remove
>> duplicates?
>> >
>> > Am 09.04.2011 13:39, schrieb Tony Morris:
>> >> The list is not sorted.
>> >>
>> >> LinkedHashSet uses variables. It also violates the rules.
>> Elements have
>> >> order, not necessarily hash-codes (ignore the fact that Java/Scala
>> >> pretends otherwise).
>> >>
>> >> On 09/04/11 20:23, HamsterofDeath wrote:
>> >>> if the list is already sorted by some ordering: new
>> treeset(yourlist,
>> >>> yourcomparator)
>> >>>
>> >>> if it is randomly sorted: new linkedhashset(yourlist)
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>> Am 09.04.2011 12:02, schrieb Tony Morris:
>> >>>> * Remove duplicate elements from a List.
>> >>>> * Elements have ordering defined.
>> >>>> * Do not use updating variables.
>> >>>> * Maintain original insertion order (though any of the
>> duplicates may be
>> >>>> removed).
>> >>>> * It may help to implement additional library support. At
>> your discretion.
>> >>>>
>> >>>> sealed trait Ordering
>> >>>> case object LT extends Ordering
>> >>>> case object EQ extends Ordering
>> >>>> case object GT extends Ordering
>> >>>>
>> >>>> trait Order[A] {
>> >>>> def compare(a1: A, a2: A): Ordering
>> >>>>
>> >>>> def contramap[B](f: B => A): Order[B] =
>> >>>> new Order[B] { def compare(b1: B, b2: B) =
>> Order.this.compare(f(b1),
>> >>>> f(b2))
>> >>>> }
>> >>>>
>> >>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]):
>> List[A] =
>> >>>> error("todo")
>> >>>>
>>
>>
>> --
>> Tony Morris
>> http://tmorris.net/
>>
>>
>>
>>
>>
>> --
>> www.sadekdrobi.com <http://www.sadekdrobi.com>
>> ʎdoɹʇuǝ
>

I admit, I hadn't tried this in scala and completely forgot about all
its caveats. I may have to reword the problem to account for this. Sorry.

On 10/04/11 03:04, HamsterofDeath wrote:
> is my solution correct?
>
> Am 09.04.2011 15:34, schrieb Tony Morris:
>> Bit slow innit?
>>
>> Not sure how to make the order thingy any clearer.
>>
>> On 09/04/2011 10:28 PM, "HamsterofDeath" > > wrote:
>>> this?
>>>
>>> (Nil /: originalList)(acc, e => if (acc.contains(e) acc else e ::
>>> acc)).reverse
>>>
>>>
>>>
>>> i am confused about that implicit order thingy.
>>>
>>> Am 09.04.2011 14:03, schrieb Sadek Drobi:
>>>> By variables you mean mutable state or any passed around state?
>>>>
>>>> On Sat, Apr 9, 2011 at 1:59 PM, Tony Morris >
>>>> >> wrote:
>>>>
>>>> a) No, the list that is returned must retain original order. b) Yes.
>>>>
>>>>
>>>> On 09/04/11 21:50, HamsterofDeath wrote:
>>>>> so there is a list and i have to a) sort it and b) remove
>>>> duplicates?
>>>>> Am 09.04.2011 13:39, schrieb Tony Morris:
>>>>>> The list is not sorted.
>>>>>>
>>>>>> LinkedHashSet uses variables. It also violates the rules.
>>>> Elements have
>>>>>> order, not necessarily hash-codes (ignore the fact that Java/Scala
>>>>>> pretends otherwise).
>>>>>>
>>>>>> On 09/04/11 20:23, HamsterofDeath wrote:
>>>>>>> if the list is already sorted by some ordering: new
>>>> treeset(yourlist,
>>>>>>> yourcomparator)
>>>>>>>
>>>>>>> if it is randomly sorted: new linkedhashset(yourlist)
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Am 09.04.2011 12:02, schrieb Tony Morris:
>>>>>>>> * Remove duplicate elements from a List.
>>>>>>>> * Elements have ordering defined.
>>>>>>>> * Do not use updating variables.
>>>>>>>> * Maintain original insertion order (though any of the
>>>> duplicates may be
>>>>>>>> removed).
>>>>>>>> * It may help to implement additional library support. At
>>>> your discretion.
>>>>>>>> sealed trait Ordering
>>>>>>>> case object LT extends Ordering
>>>>>>>> case object EQ extends Ordering
>>>>>>>> case object GT extends Ordering
>>>>>>>>
>>>>>>>> trait Order[A] {
>>>>>>>> def compare(a1: A, a2: A): Ordering
>>>>>>>>
>>>>>>>> def contramap[B](f: B => A): Order[B] =
>>>>>>>> new Order[B] { def compare(b1: B, b2: B) =
>>>> Order.this.compare(f(b1),
>>>>>>>> f(b2))
>>>>>>>> }
>>>>>>>>
>>>>>>>> def removeDuplicates[A](a: List[A])(implicit o: Order[A]):
>>>> List[A] =
>>>>>>>> error("todo")
>>>>>>>>
>>>>
>>>> --
>>>> Tony Morris
>>>> http://tmorris.net/
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> www.sadekdrobi.com
>>
>>>> ʎdoɹʇuǝ
>

Here's a lame version that uses a sieve and tail recursion:
def removeDuplicates[A](a : List[A])(implicit o : Order[A]): List[A] = {   def addToSieve(f : A => Boolean, x : A) : (A => Boolean) = {      y =>       o.compare(x,y) match {         case EQ => true         case _ => f(y)       }  }           def go(sieve : A => Boolean, cur : List[A], rest : List[A]) : List[A] = rest match {     case Nil => cur     case x :: xs if seive(x) => go(seive, cur, xs)    case x :: xs => go(addToSeive(seive, x), x :: cur, xs)  }  go((ignore=>false), List(), a).reverse }
I know you put contramap in there for a reason, and it's haunting the corners of my brain at this hour.   I'll take another crack tomorrow :)
On Sat, Apr 9, 2011 at 6:02 AM, Tony Morris <tonymorris@gmail.com> wrote:

* Remove duplicate elements from a List.
* Elements have ordering defined.
* Do not use updating variables.
* Maintain original insertion order (though any of the duplicates may be
removed).
* It may help to implement additional library support. At your discretion.

sealed trait Ordering
case object LT extends Ordering
case object EQ extends Ordering
case object GT extends Ordering

trait Order[A] {
 def compare(a1: A, a2: A): Ordering

 def contramap[B](f: B => A): Order[B] =
   new Order[B] { def compare(b1: B, b2: B) = Order.this.compare(f(b1),
f(b2))
}

def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
error("todo")

--
Tony Morris
http://tmorris.net/

I only put contramap there out of compulsion -- similar to how others
might put a contravariant annotation.

I am trying to reformulate the question to provoke the intended solution

I'm thinking the result Tony's looking for might be something like:

def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
    a.head :: removeDuplicates(a.tail filter { o.compare(_, a.head) != EQ })

Brian Maso

On Sun, Apr 10, 2011 at 12:15 AM, Tony Morris <tonymorris@gmail.com> wrote:

I only put contramap there out of compulsion -- similar to how others
might put a contravariant annotation.

I am trying to reformulate the question to provoke the intended solution

So I didn't get my recursion terminating condition check right the first time. Here's the correct version -- sadly more than 1 line, so maybe there's a more condensed way of writing this:

def removeDuplicates[A](a: List[A])(implicito: Order[A]): List[A] =
  a match {
    case head :: rest => head :: removeDuplicates(rest filter { o.compare(_, head) != EQ})
    case _ => List()
    }

Brian Maso

On Mon, Apr 11, 2011 at 2:45 PM, Brian Maso <brian@blumenfeld-maso.com> wrote:

I'm thinking the result Tony's looking for might be something like:

def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =
    a.head :: removeDuplicates(a.tail filter { o.compare(_, a.head) != EQ })

Brian Maso

On Sun, Apr 10, 2011 at 12:15 AM, Tony Morris <tonymorris@gmail.com> wrote:

I only put contramap there out of compulsion -- similar to how others
might put a contravariant annotation.

I am trying to reformulate the question to provoke the intended solution

v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);}

I think this is not efficient (n^2) and also not tail-recursive (will blow stack).

It’s not hard to write a n*log-n tail-recursive implementation, just not sure what Tony was looking for exactly.

 

 

val exampleList = List(7, 1, 3, 1, 4, 4, 9)

val expectedRes = List(7, 1, 3, 4, 9)

 

def exercise[A](l:List[A]):List[A] = {

  @scala.annotation.tailrec

  def exercise(l:List[A], acc:List[A], s:Set[A]):List[A] = l match {

    case x::xs =>

      if(s(x)) exercise(xs, acc, s)

      else exercise(xs, x::acc, s + x)

    case Nil  => acc.reverse

  }

  exercise(l, Nil, Set())

}

 

println( exercise(exampleList) == expectedRes )

 

 

This should be ok even if the list has, let’s say, one million elements (it might just take a few seconds).

However, I am sure Tony was looking for a very different implementation….

 

 

Tommaso

 

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of Brian Maso
Sent: 11 April 2011 22:59
To: tmorris@tmorris.net
Cc: Tony Morris; Josh Suereth; scala-user
Subject: Re: [scala-user] small puzzle

 

So I didn't get my recursion terminating condition check right the first time. Here's the correct version -- sadly more than 1 line, so maybe there's a more condensed way of writing this:

def removeDuplicates[A](a: List[A])(implicito: Order[A]): List[A] =
  a match {
    case head :: rest => head :: removeDuplicates(rest filter { o.compare(_, head) != EQ})
    case _ => List()
    }

Brian Maso

On Mon, Apr 11, 2011 at 2:45 PM, Brian Maso <brian@blumenfeld-maso.com> wrote:

I'm thinking the result Tony's looking for might be something like:

def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =

    a.head :: removeDuplicates(a.tail filter { o.compare(_, a.head) != EQ })

Brian Maso

 

On Sun, Apr 10, 2011 at 12:15 AM, Tony Morris <tonymorris@gmail.com> wrote:

I only put contramap there out of compulsion -- similar to how others
might put a contravariant annotation.

I am trying to reformulate the question to provoke the intended solution

On 12/04/11 09:19, Tommaso Galleri wrote:

E02CB9B2777CF8459C86C49B48C48EC60833F763 [at] exchange [dot] bjss [dot] co [dot] uk" type="cite"> just not sure what Tony was looking for exactly.

Yeah sorry about that. I went ahead and solved it with scala in the way I was intending and I spent a lot of the time jumping through hoops, which I didn't foresee and now expect would distract from the purpose.

Essentially, I wanted to introduce the idea of a monadic fold through the State monad and perhaps encouragement the development of an intuition for it. Specifically, folding through the list, but maintaining state (a Set that you can inspect and insert into) while you go. This much seems "kind of natural" to most people, but how would you implement it?

Aside from a few facts:
* a monadic fold is not included in the standard library
* foldRight may use stack or use foldLeft with reverse or whatever -- I am going with foldRight
* State is not in the standard library
* Many people are probably used to using variables (i.e. to hold a mutable Set or var to immutable Set) instead of State -- the purpose of the exercise is to demonstrate that the variables are not necessary.
* I learned that calling TreeSet.insert when the element is present produces an error due to an assertion in the library code (WTF?) so I have had to modify my desired solution accordingly. I actually went ahead and wrote a more appropriate Set implementation, but it was more of a distraction, so it was omitted.


Here is a naive solution without use of explicit State, but without variables by explicit pairing and passing the state value around with the fold:

  a.foldRight((Nil: List[A], TreeSet.empty)) {
    case (a, (z, s)) => if(s contains a) (z, s) else (a::z, s insert a)
  }._1

Notice the pairing of the List and TreeSet and the manual passing around of these values. The Set is discarded at the end to produce the result (._1).

Now suppose a minimal State implementation with its monad (flatMap+pure):

case class State[S, A](run: S => (A, S)) {
  def map[B](f: A => B) =
   State[S, B](s => {
     val (a, ss) = run(s)
     (f(a), ss)
   })

  def flatMap[B](f: A => State[S, B]) =
    State[S, B](s => {
      val (a, ss) = run(s)
      f(a) run ss
    })

  def eval(s: S) = run(s)._1
}

object State {
  def pure[S, A](a: => A) =
    State[S, A](s => (a, s))
}


Our (still naive) solution now becomes a little tidier since we can exploit the monad (call to flatMap):

  a.foldRight(pure[TreeSet[A], List[A]](Nil)) {
    case (a, s) =>
      s flatMap (as => State(z => if(z contains a) (as, z) else (a::as, z insert a)))
  } eval TreeSet.empty

Now let us introduce a monad interface with the State[S, _] implementation. The type-lambda is simply because State is a binary type constructor and we wish to curry it and apply one type variable to give us a unary type constructor.

trait FlatMap[F[_]] {
  def pure[A](a: => A): F[A]
  def flatMap[A, B](f: A => F[B], a: F[A]): F[B]
  final def map[A, B](f: A => B, a: F[A]): F[B] =
    flatMap((a: A) => pure(f(a)), a)
}

object FlatMap {
  implicit def StateMonad[S]: FlatMap[({type λ[α]=State[S, α]})#λ] = new FlatMap[({type λ[α]=State[S, α]})#λ] {
    def pure[A](a: => A) =
      State.pure(a)
    def flatMap[A, B](f: A => State[S, B], a: State[S, A]) =
      a flatMap f
  }
}

Now we can add a foldRight method that "threads" through any monad (FlatMap) implementation:

case class RichList[A](a: List[A]) {
  def foldRightM[F[_], B](z: B)(f: (A, B) => F[B])(implicit m: FlatMap[F]): F[B] =
    a.foldLeft[B => F[B]](m pure _)((b, a) => t => m flatMap (b, f(a, t)))(z)

  def foldLeftM[F[_], B](z: B)(f: (B, A) => F[B])(implicit m: FlatMap[F]): F[B] =
    a.foldRight[B => F[B]](m pure _)((a, b) => t => m flatMap (b, f(t, a)))(z)
}

object RichList {
  implicit def ListRich[A](a: List[A]): RichList[A] = RichList(a)
}

Note that fold*M has the same signature as fold* except that F appears in all the return value positions. The value for F (such as State[S, _]) is "threaded" through the fold.

This allows the following solution:

a.foldRightM[({type λ[α]=State[TreeSet[A], α]})#λ, List[A]](Nil) {
    case (a, s) =>
      State(z => if(s contains a) (s, z) else (a::s, z insert a))
  } eval TreeSet.empty

Type-annotations aside (we could specialise them if need be), we have a very straight-forward solution to the problem, demonstrating the State monad.

Sorry it wasn't a little more helpful than I originally predicted :(

Here is a working solution:
https://bitbucket.org/dibblego/miscellaneous/src/tip/SmallPuzzle.scala

-- 
Tony Morris
http://tmorris.net/

On Mon, Apr 11, 2011 at 4:19 PM, Tommaso Galleri <Tommaso.Galleri@bjss.com> wrote:

I think this is not efficient (n^2) and also not tail-recursive (will blow stack). 

It’s not hard to write a n*log-n tail-recursive implementation, just not sure what Tony was looking for exactly.

 

 

val exampleList = List(7, 1, 3, 1, 4, 4, 9)

val expectedRes = List(7, 1, 3, 4, 9)

 

def exercise[A](l:List[A]):List[A] = {

  @scala.annotation.tailrec

  def exercise(l:List[A], acc:List[A], s:Set[A]):List[A] = l match {

    case x::xs =>

      if(s(x)) exercise(xs, acc, s)

      else exercise(xs, x::acc, s + x)

    case Nil  => acc.reverse

  }

  exercise(l, Nil, Set())

}

 

println( exercise(exampleList) == expectedRes )

Well, I don't see how you could do better than n log n with tail recursive calls. Good job.

Though you'd need a minor tweek to make your code work correctly: the "if(s(x))" test isn't using the Order[A], so its not going to yield correct results when {(x,y) => o.compare(x,y) == EQ} doesn't agree with {(x,y) => x.equal(y)}. You'd need to clean that up before its a completely correct solution. I think the easiest way to do that with your code would be to make a scala.math.Ordering out of Tony's Order, and use that to create a TreeSet. I think that's basically your idea, right? I guess really its just a matter of what Set instance gets passed in to the initial call to the nested exercise() function.

Brian Maso

 

 

This should be ok even if the list has, let’s say, one million elements (it might just take a few seconds).

However, I am sure Tony was looking for a very different implementation….

 

 

Tommaso

 

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of Brian Maso
Sent: 11 April 2011 22:59
To: tmorris@tmorris.net
Cc: Tony Morris; Josh Suereth; scala-user
Subject: Re: [scala-user] small puzzle

 

So I didn't get my recursion terminating condition check right the first time. Here's the correct version -- sadly more than 1 line, so maybe there's a more condensed way of writing this:

def removeDuplicates[A](a: List[A])(implicito: Order[A]): List[A] =
  a match {
    case head :: rest => head :: removeDuplicates(rest filter { o.compare(_, head) != EQ})
    case _ => List()
    }

Brian Maso

On Mon, Apr 11, 2011 at 2:45 PM, Brian Maso <brian@blumenfeld-maso.com> wrote:

I'm thinking the result Tony's looking for might be something like:

def removeDuplicates[A](a: List[A])(implicit o: Order[A]): List[A] =

    a.head :: removeDuplicates(a.tail filter { o.compare(_, a.head) != EQ })

Brian Maso

 

On Sun, Apr 10, 2011 at 12:15 AM, Tony Morris <tonymorris@gmail.com> wrote:

I only put contramap there out of compulsion -- similar to how others
might put a contravariant annotation.

I am trying to reformulate the question to provoke the intended solution

Ya know, I was just going to say that this problem looks like an obvious candidate for a State Monad[1].
Seriously, this is great stuff, but it begs the question: why?  It's not just because you can, that's obvious.  What problem were you wrestling with that provoked this particular approach to solving the problem instead of the several other seemingly trivial "solutions" provided in this thread?  Was this just for education or did this come up in your [Scala] work?  Merely curious.
Although I already mentioned it, I say so again: great stuff, thanks!
--
Jim Powers
[1] Actually, my zombified body is collecting the bits of my brain that splattered over everything after my head exploded reading this post.

On 12/04/11 11:02, Jim Powers wrote:
> Ya know, I was just going to say that this problem looks like an
> obvious candidate for a State Monad[1].
>
> Seriously, this is great stuff, but it begs the question: why? It's
> not just because you can, that's obvious. What problem were you
> wrestling with that provoked this particular approach to solving the
> problem instead of the several other seemingly trivial "solutions"
> provided in this thread? Was this just for education or did this come
> up in your [Scala] work? Merely curious.
>
> Although I already mentioned it, I say so again: great stuff, thanks!
>

On Mon, Apr 11, 2011 at 6:40 PM, Tony Morris wrote:
> Type-annotations aside (we could specialise them if need be), we have a very
> straight-forward solution to the problem, demonstrating the State monad.
>
> Sorry it wasn't a little more helpful than I originally predicted :(

You succeeded here Tony. For some reason I could never grasp the use
case for the State Monad, but I use folds a lot to carry state through
a Monad. Showing examples of going from one to the other finally makes
it click for me. Most State tutorials out there jump right into using
the State Monad without showing me the code I'm writing right now that
can take advantage of it.

Thanks!

On Apr 12, 2011, at 3:08, Tony Morris wrote:

> On 12/04/11 11:02, Jim Powers wrote:
>> Ya know, I was just going to say that this problem looks like an
>> obvious candidate for a State Monad[1].
>>
>> Seriously, this is great stuff, but it begs the question: why? It's
>> not just because you can, that's obvious. What problem were you
>> wrestling with that provoked this particular approach to solving the
>> problem instead of the several other seemingly trivial "solutions"
>> provided in this thread? Was this just for education or did this come
>> up in your [Scala] work? Merely curious.
>>
>> Although I already mentioned it, I say so again: great stuff, thanks!
>>