recursive structural types and alternatives

do as the compiler says, add a result type to the recursive method.

Am 03.08.2011 20:41, schrieb Antoras:
> I have a method which expects different types but the same methods.
> For example I have a List and an own implementation of a collection:
>
> def meth[A](xs: List[A]) = {...}
> def meth[A](xs: MyCollection[A]) = {...}
>
> Both methods do exactly the same but there is no super type for List
> and MyCollection. Thus I can't rewrite the method to
>
> def meth[A](xs: SuperType[A])
>
> Now, I tried to create a structural type
>
> type SingleChained[A] = {
> def head: A
> def tail: SingleChained[A]
> }
>
> But it does not compile. The error message is: "recursive method tail
> needs result type".
>
> Why is there this restriction and what can I do to reduce code
> duplication?
>

Type inference in Scala is not able to find your return type if you use a recursive method, which is quite logical : if your recursive fucntion has n terminal cases, their types will be found easily, but the recursive cases won't have a defined type, except the one you are trying to infer. Thus to certify a return type for the function, you need the return type of the function. Finding a type in a recursive function can not afford to be a recursive process, so the type inferer gives up on this. Maybe some hack could solve most of the recursion cases, but since recursion schemes always comes with the worst corner cases, it probably is better to force the user to type the recursive functions, as a general rule...

2011/8/3 HamsterofDeath <h-star@gmx.de>

do as the compiler says, add a result type to the recursive method.

Am 03.08.2011 20:41, schrieb Antoras:
> I have a method which expects different types but the same methods.
> For example I have a List and an own implementation of a collection:
>
> def meth[A](xs: List[A]) = {...}
> def meth[A](xs: MyCollection[A]) = {...}
>
> Both methods do exactly the same but there is no super type for List
> and MyCollection. Thus I can't rewrite the method to
>
> def meth[A](xs: SuperType[A])
>
> Now, I tried to create a structural type
>
> type SingleChained[A] = {
>   def head: A
>   def tail: SingleChained[A]
> }
>
> But it does not compile. The error message is: "recursive method tail
> needs result type".
>
> Why is there this restriction and what can I do to reduce code
> duplication?
>

--
Alex REPAIN
ENSEIRB-MATMECA - student
TECHNICOLOR R&D - intern
BORDEAUX I      - master's student
SCALA           - enthusiast

There is a return type. It is the type itself.

Ok, that make sense.

What else can I do to reduce code duplication?

Why not simply parameterize the collection itself.

Use def meth[A](xs: A) = {...}

--
Stefan

2011/8/4 Antoras :
> Ok, that make sense.
>
> What else can I do to reduce code duplication?
>

Am Do 04 Aug 2011 11:38:49 CEST, Stefan Langer schrieb:
> Why not simply parameterize the collection itself.
>
> Use def meth[A](xs: A) = {...}
>
> --
> Stefan

I need to call some methods of the delivered type. The methods I need
are the same for all types, but there is no supertype.

On Wed, Aug 03, 2011 at 08:41:35PM +0200, Antoras said
> I have a method which expects different types but the same methods. For
> example I have a List and an own implementation of a collection:
>
> def meth[A](xs: List[A]) = {...}
> def meth[A](xs: MyCollection[A]) = {...}
>
> Both methods do exactly the same but there is no super type for List and
> MyCollection. Thus I can't rewrite the method to
>
> def meth[A](xs: SuperType[A])
>
> Now, I tried to create a structural type
>
> type SingleChained[A] = {
> def head: A
> def tail: SingleChained[A]
> }
>
> But it does not compile. The error message is: "recursive method tail
> needs result type".
>
> Why is there this restriction and what can I do to reduce code duplication?

One possibility is to sidestep the structural type altogether and use a
typeclass. It would look something like the code below. To extends it to
more classes you just need to add a class like MyCollectionIsListLike
and an implicit def like myCollectionIsListLike. If you'd like to know
more of how it works, I can post a followup.

trait ListLike[C[_], T] {
def head(c: C[T]): T
def tail(c: C[T]): C[T]
}

case class MyCollection[T](head: T, tail: MyCollection[T])

object ListLike {
class ListIsListLike[T] extends ListLike[List, T] {
def head(c: List[T]) = c.head
def tail(c: List[T]) = c.tail
}
class MyCollectionIsListLike[T] extends ListLike[MyCollection, T] {
def head(c: MyCollection[T]) = c.head
def tail(c: MyCollection[T]) = c.tail
}
implicit def listIsListLike[T] = new ListIsListLike[T]
implicit def myCollectionIsListLike[T] = new MyCollectionIsListLike[T]

def head[T,C[_]](c: C[T])(implicit ll: ListLike[C, T]): T = ll.head(c)
def tail[T,C[_]](c: C[T])(implicit ll: ListLike[C, T]): C[T] = ll.tail(c)

type Of[T] = { type Collection[C[_]] = ListLike[C,T] }
}

object ListLikeTest extends App {
def meth[T,C[_] : ListLike.Of[T]#Collection](xs: C[T]) = ListLike.head(ListLike.tail(xs))

println(meth(List(1,2,3,4)))
println(meth(MyCollection('a',MyCollection('b', null))))
}

Might make MyCollection implement Seq, then just do
def meth[A](xs: Seq[A]): SomeType = {...}

On Aug 3, 11:41 am, Antoras wrote:
> I have a method which expects different types but the same methods. For
> example I have a List and an own implementation of a collection:
>
> def meth[A](xs: List[A]) = {...}
> def meth[A](xs: MyCollection[A]) = {...}
>
> Both methods do exactly the same but there is no super type for List and
> MyCollection. Thus I can't rewrite the method to
>
> def meth[A](xs: SuperType[A])
>
> Now, I tried to create a structural type
>
> type SingleChained[A] = {
>    def head: A
>    def tail: SingleChained[A]
>
> }
>
> But it does not compile. The error message is: "recursive method tail
> needs result type".
>
> Why is there this restriction and what can I do to reduce code duplication?

i could not believe that

type SingleChained[A] = {
def head: A
def tail: SingleChained[A]

does not compile so i checked.
why doesn't it? the error message doesn't make sense

-------- Original-Nachricht --------
> Datum: Thu, 4 Aug 2011 08:06:49 -0700 (PDT)
> Von: Joshua Gooding
> An: scala-user
> Betreff: [scala-user] Re: recursive structural types and alternatives

> Might make MyCollection implement Seq, then just do
> def meth[A](xs: Seq[A]): SomeType = {...}
>
> On Aug 3, 11:41 am, Antoras wrote:
> > I have a method which expects different types but the same methods. For
> > example I have a List and an own implementation of a collection:
> >
> > def meth[A](xs: List[A]) = {...}
> > def meth[A](xs: MyCollection[A]) = {...}
> >
> > Both methods do exactly the same but there is no super type for List and
> > MyCollection. Thus I can't rewrite the method to
> >
> > def meth[A](xs: SuperType[A])
> >
> > Now, I tried to create a structural type
> >
> > type SingleChained[A] = {
> >    def head: A
> >    def tail: SingleChained[A]
> >
> > }
> >
> > But it does not compile. The error message is: "recursive method tail
> > needs result type".
> >
> > Why is there this restriction and what can I do to reduce code
> duplication?

Because type can't referrer to them selves. I don't quite understand
why.

On Aug 4, 8:19 am, "Dennis Haupt" wrote:
> i could not believe that
>
> type SingleChained[A] = {
>                 def head: A
>                 def tail: SingleChained[A]
>
> does not compile so i checked.
> why doesn't it? the error message doesn't make sense
>
> -------- Original-Nachricht --------
>
>
>
>
>
>
>
> > Datum: Thu, 4 Aug 2011 08:06:49 -0700 (PDT)
> > Von: Joshua Gooding
> > An: scala-user
> > Betreff: [scala-user] Re: recursive structural types and alternatives
> > Might make MyCollection implement Seq, then just do
> > def meth[A](xs: Seq[A]): SomeType = {...}
>
> > On Aug 3, 11:41 am, Antoras wrote:
> > > I have a method which expects different types but the same methods. For
> > > example I have a List and an own implementation of a collection:
>
> > > def meth[A](xs: List[A]) = {...}
> > > def meth[A](xs: MyCollection[A]) = {...}
>
> > > Both methods do exactly the same but there is no super type for List and
> > > MyCollection. Thus I can't rewrite the method to
>
> > > def meth[A](xs: SuperType[A])
>
> > > Now, I tried to create a structural type
>
> > > type SingleChained[A] = {
> > >    def head: A
> > >    def tail: SingleChained[A]
>
> > > }
>
> > > But it does not compile. The error message is: "recursive method tail
> > > needs result type".
>
> > > Why is there this restriction and what can I do to reduce code
> > duplication?

Because Scala doesn't do 'Hindley-Milner type inference' which is
multipass, but a simple one pass in the forward direction 'local type
inference'. After evaluating the recursive function the type inferrer
doesn't go back to fill in the return type.

I am not a type system expert, but making Hindley-Milner's type
inference supporting OO (overloading, subtyping and all those things)
at the same time is still hard to implement.

So therefore in Scala function parameters (both recursive and non-
recursive functions) and return values of recursive functions must
always be type annotated explicitly.

See daniel's comment:
http://www.scala-lang.org/node/4654#comment-19204

On 04.08.2011 17:06, Joshua Gooding wrote:
> Might make MyCollection implement Seq, then just do
> def meth[A](xs: Seq[A]): SomeType = {...}
Thanks for your answer, but thats not what I'm looking for. I don't want
to extend the standard library, I'm searching for a way to support the
standard library as good as I can.

On 04.08.2011 15:20, Geoff Reedy wrote:
> One possibility is to sidestep the structural type altogether and use a
> typeclass. It would look something like the code below. To extends it to
> more classes you just need to add a class like MyCollectionIsListLike
> and an implicit def like myCollectionIsListLike. If you'd like to know
> more of how it works, I can post a followup.
>
> trait ListLike[C[_], T] {
> def head(c: C[T]): T
> def tail(c: C[T]): C[T]
> }
>
> case class MyCollection[T](head: T, tail: MyCollection[T])
>
> object ListLike {
> class ListIsListLike[T] extends ListLike[List, T] {
> def head(c: List[T]) = c.head
> def tail(c: List[T]) = c.tail
> }
> class MyCollectionIsListLike[T] extends ListLike[MyCollection, T] {
> def head(c: MyCollection[T]) = c.head
> def tail(c: MyCollection[T]) = c.tail
> }
> implicit def listIsListLike[T] = new ListIsListLike[T]
> implicit def myCollectionIsListLike[T] = new MyCollectionIsListLike[T]
>
> def head[T,C[_]](c: C[T])(implicit ll: ListLike[C, T]): T = ll.head(c)
> def tail[T,C[_]](c: C[T])(implicit ll: ListLike[C, T]): C[T] = ll.tail(c)
>
> type Of[T] = { type Collection[C[_]] = ListLike[C,T] }
> }
>
> object ListLikeTest extends App {
> def meth[T,C[_] : ListLike.Of[T]#Collection](xs: C[T]) = ListLike.head(ListLike.tail(xs))
>
> println(meth(List(1,2,3,4)))
> println(meth(MyCollection('a',MyCollection('b', null))))
> }
That works great! But it is a bit unhandly to use. Due to the access of
the inner type Collection, the method signature of meth looks a bit
ugly. Furthermore it would be great if the methods head and tail could
be accessed through xs.head ad xs.tail.

It is an interesting solution, but I don't know if it is what I'm
looking for.

What does this have to do with type inference? We're being fully explicit about the types. The problem is simply referencing it within its own definition.I ran into this limitation once as well.

On Thu, Aug 4, 2011 at 2:55 PM, Dave <dave.mahabiersing@hotmail.com> wrote:

Because Scala doesn't do 'Hindley-Milner type inference' which is
multipass, but a simple one pass in the forward direction 'local type
inference'. After evaluating the recursive function the type inferrer
doesn't go back to fill in the return type.

I am not a type system expert, but making Hindley-Milner's type
inference supporting OO (overloading, subtyping and all those things)
at the same time is still hard to implement.

So therefore in Scala function parameters (both recursive and non-
recursive functions) and return values of recursive functions must
always be type annotated explicitly.

See daniel's comment:
http://www.scala-lang.org/node/4654#comment-19204

2011/8/5 Naftoli Gugenheim <naftoligug@gmail.com>

What does this have to do with type inference?

As explained by Dave, the type inference scheme is one-pass, no backtracking. When parsing a recursive function without annotated return type, the type inferrer will only fill the return type once it inferred it from the function content. Here the content calls the function itself, which has no return type inferred at this time. A general return type can not be inferred. We could hack by saying that the terminal cases return types are sufficient, but that trick would not work for mutually-recursive functions, or n-function recursive schemes in general.

 

We're being fully explicit about the types. The problem is simply referencing it within its own definition. I ran into this limitation once as well.

On Thu, Aug 4, 2011 at 2:55 PM, Dave <dave.mahabiersing@hotmail.com> wrote:

Because Scala doesn't do 'Hindley-Milner type inference' which is
multipass, but a simple one pass in the forward direction 'local type
inference'. After evaluating the recursive function the type inferrer
doesn't go back to fill in the return type.

I am not a type system expert, but making Hindley-Milner's type
inference supporting OO (overloading, subtyping and all those things)
at the same time is still hard to implement.

So therefore in Scala function parameters (both recursive and non-
recursive functions) and return values of recursive functions must
always be type annotated explicitly.

See daniel's comment:
http://www.scala-lang.org/node/4654#comment-19204

--
Alex REPAIN
ENSEIRB-MATMECA - student
TECHNICOLOR R&D - intern
BORDEAUX I      - master's student
SCALA           - enthusiast

Yes

Breakdown how I see it:

type SingleChained[A] = {
def head: A
def tail: X
}

When it's on positions X it ecounters SingleChained[A] but at that
moment it is not defined until after the closing curly brace.
It needs a second pass to fill in X with SingleChained[A] which
Scala's local type inference does not provide.

But the same is for recursive functions we all know.

scala> object InferenceTest2 {
| def fac(n: Int) = if (n == 0) 1 else n * fac(n - 1)
| }
:8: error: recursive method fac needs result type
def fac(n: Int) = if (n == 0) 1 else n * fac(n - 1)
^

scala> object InferenceTest2 {
| def fac(n: Int) : Int = if (n == 0) 1 else n * fac(n - 1)
| }
defined module InferenceTest2

See also:
http://www.scala-lang.org/node/127

On 5 aug, 01:29, Alex Repain wrote:
> 2011/8/5 Naftoli Gugenheim
>
> > What does this have to do with type *inference*?
>
> As explained by Dave, the type inference scheme is one-pass, no
> backtracking. When parsing a recursive function without annotated return
> type, the type inferrer will only fill the return type once it inferred it
> from the function content. Here the content calls the function itself, which
> has no return type inferred at this time. A general return type can not be
> inferred. We could hack by saying that the terminal cases return types are
> sufficient, but that trick would not work for mutually-recursive functions,
> or n-function recursive schemes in general.
>
>
>
>
>
> > We're being fully explicit about the types. The problem is simply
> > referencing it within its own definition.
> > I ran into this limitation once as well.
>
> > On Thu, Aug 4, 2011 at 2:55 PM, Dave wrote:
>
> >> Because Scala doesn't do 'Hindley-Milner type inference' which is
> >> multipass, but a simple one pass in the forward direction 'local type
> >> inference'. After evaluating the recursive function the type inferrer
> >> doesn't go back to fill in the return type.
>
> >> I am not a type system expert, but making Hindley-Milner's type
> >> inference supporting OO (overloading, subtyping and all those things)
> >> at the same time is still hard to implement.
>
> >> So therefore in Scala function parameters (both recursive and non-
> >> recursive functions) and return values of recursive functions must
> >> always be type annotated explicitly.
>
> >> See daniel's comment:
> >>http://www.scala-lang.org/node/4654#comment-19204
>
> --
> *Alex REPAIN*
> ENSEIRB-MATMECA - student
> TECHNICOLOR R&D - intern
> BORDEAUX I      - master's student
> SCALA           - enthusiast- Tekst uit oorspronkelijk bericht niet weergeven -
>
> - Tekst uit oorspronkelijk bericht weergeven -

Further philosophing:
More accurate is - since we are in a recursive type - the return type
should actually be a return kind.
A kind is a type of types
In Haskell there is the built-in kind * which means 'a concrete type'
I haven't found anything like that in Scala.

So it would be nice if the local type inferencer and the lexer/parser
could handle this and the pattern is analogue to 'normal' recursive
functions but although it looks simple on the outside it maybe
difficult to implement in the inside for instance dealing with OO and
so on:

type SingleChained[A]: * = {
def head: A
def tail: SingleChained[A]
}

So here ': *' means the result kind is a concrete type

Then the breakdown becomes:

type SingleChained[A]: * = {
def head: A
def tail: X
}

So the local type inferencer knows now at the position of X that the
return kind of X is a concrete type in one pass.

Sorry for bringing this old thread to the top, I have difficulties in
understanding the whole issue.

>type SingleChained[A] = {
> def head: A
> def tail: X
>
>}
>
>When it's on positions X it ecounters SingleChained[A] but at that
>moment it is not defined until after the closing curly brace.
>It needs a second pass to fill in X with SingleChained[A] which
>Scala's local type inference does not provide.

I understand the problem why SingleChained[A] is not yet defined and
thus fails to compile.
But what is the difference in a class definition:

abstract class SingleChained[A]{
def head: A
def tail: SingleChained[A]
}

would surely compile fine. If here the type is already know before the
closing curly brace, I don't understand why this isn't possible with a
type alias.

most likely it's jsut that nobody has implemented it yet

-------- Original-Nachricht --------
> Datum: Thu, 25 Aug 2011 08:14:27 -0700 (PDT)
> Von: "Daniel D."
> An: scala-user
> Betreff: [scala-user] Re: recursive structural types and alternatives

> Sorry for bringing this old thread to the top, I have difficulties in
> understanding the whole issue.
>
>
> >type SingleChained[A] = {
> > def head: A
> > def tail: X
> >
> >}
> >
> >When it's on positions X it ecounters SingleChained[A] but at that
> >moment it is not defined until after the closing curly brace.
> >It needs a second pass to fill in X with SingleChained[A] which
> >Scala's local type inference does not provide.
>
> I understand the problem why SingleChained[A] is not yet defined and
> thus fails to compile.
> But what is the difference in a class definition:
>
> abstract class SingleChained[A]{
> def head: A
> def tail: SingleChained[A]
> }
>
> would surely compile fine. If here the type is already know before the
> closing curly brace, I don't understand why this isn't possible with a
> type alias.

This is how I see it:
There is a clear difference and that is the assignment symbol =
Compare between:
recursive type alias
====================
type SingleChained[A] = {
def head: A
def tail: SingleChained[A]
}

recursive method
================
def fac(n: Int) = if (n == 0) 1 else n * fac(n - 1)

and:

recursive class definition
==========================
abstract class SingleChained[A]{
def head: A
def tail: SingleChained[A]
}

In the latter there is no assignment and I don't know about what the
return value of a class definition is. The REPL doesn't show a return
type and a return value
only "defined class SingleChained" which is just a confirmation of an
action.

Class definitions are pure statements (there is no return type, no
return value}
The right hand side (after the =) of the type alias definitions and
method definitions are expressions ( there is always a return type and
a return value)
Even a return type Unit has a return value ()
The difference between a statement and an expression is that you can
put an expression everywhere where you can put a value with a
compatible type, because an expression always returns a value.

I think that the type inferencer doesn't work for pure statements
(like class definitions etcetera), because it doesn't make sense to do
that: there is nothing to infer.
Except of course for expressions inside a class definition.

On 25 aug, 17:14, "Daniel D."
wrote:
> Sorry for bringing this old thread to the top, I have difficulties in
> understanding the whole issue.
>
> >type SingleChained[A] = {
> >     def head: A
> >     def tail: X
>
> >}
>
> >When it's on positions X it ecounters SingleChained[A] but at that
> >moment it is not defined until after the closing curly brace.
> >It needs a second pass to fill in X with SingleChained[A] which
> >Scala's local type inference does not provide.
>
> I understand the problem why SingleChained[A] is not yet defined and
> thus fails to compile.
> But what is the difference in a class definition:
>
> abstract class SingleChained[A]{
> def head: A
> def tail: SingleChained[A]
>
> }
>
> would surely compile fine. If here the type is already know before the
> closing curly brace, I don't understand why this isn't possible with a
> type alias.