3 ms·

> arbitrarily nested lists "Cool" as it might be, please don't inflict it on others.

by mbid 8y ago

baddox 8y ago
I’m not aware of the specific type features the commenter was mentioning, but that doesn’t sound too different than a tree or graph data structure.
- joshlemer 8y ago
  I believe the commenter may have been talking about what I've seen called fix-point recursion, and it is exactly as you say, it is for representing arbitrarily nested tree structures in a statically typed way. For example in scala, maybe you have data about Users case class User(id: Long, name: String, friends: List[User]) However, this structures is kinda inflexible, you don't always want to deal with an entire tree of users at a time. Maybe, you just want to have the friend userids, so you can introduce a type parameter for the recursive data case class User[Friend](id: Long, name: String, friends: List[Friend]) and then you can have a User[Long] which contains the friend ids, or User[String] which contains the friend names. However, if you want to go back and have the list be of Users themselves, you would have to know statically how deep the tree you're returning is. For example, this type would include full user information down to the grandchild level, but then terminate with the ids: User[User[User[Long]]] This is actually very useful! Sometimes we may want exactly this deep of a structure. If we want to get an arbitrarily deep tree of users, we would need to have an infinitely nested type like User[User[User[User[User[User[...]]]]]] which is of course impossible. So instead, people have a work-around using higher-kinded types, called `Fix`: case class Fix[F[_]](unfix: F[Fix[F]]) This signature may look scary, but if you apply it to User you get Fix[User](unfix: User[Fix[User]]) and all this means is that now we can deal with Fix[User] which means the same thing as User[User[...]]. You can construct one such Fix[User] differing levels like so: Fix( User( id = 1L, name = "Josh", friends = List( Fix( User( id = 2L, name = "John", friends = List( Fix( User( id = 3L, name = "Stacey" friends = List.empty ) ) ) ), Fix( User( id = 4L name = "Mary" friends = List.empty ) ) ) )
harpocrates 8y ago
Some other applications are more interesting. For instance, finger trees (which back the efficient implementations of a handful of immutable data structures) usually are implemented in a way that requires polymorphic recursion.
catnaroek 8y ago
I don't see anything wrong with rose trees: datatype 'a tree = T of 'a * 'a tree list Do you?

> arbitrarily nested lists "Cool" as it might be, please don't inflict it on others.

by mbid 8y ago

> arbitrarily nested lists "Cool" as it might be, please don't inflict it on others.

I’m not aware of the specific type features the commenter was mentioning, but that doesn’t sound too different than a tree or graph data structure.

joshlemer 8y ago
I believe the commenter may have been talking about what I've seen called fix-point recursion, and it is exactly as you say, it is for representing arbitrarily nested tree structures in a statically typed way. For example in scala, maybe you have data about Users case class User(id: Long, name: String, friends: List[User]) However, this structures is kinda inflexible, you don't always want to deal with an entire tree of users at a time. Maybe, you just want to have the friend userids, so you can introduce a type parameter for the recursive data case class User[Friend](id: Long, name: String, friends: List[Friend]) and then you can have a User[Long] which contains the friend ids, or User[String] which contains the friend names. However, if you want to go back and have the list be of Users themselves, you would have to know statically how deep the tree you're returning is. For example, this type would include full user information down to the grandchild level, but then terminate with the ids: User[User[User[Long]]] This is actually very useful! Sometimes we may want exactly this deep of a structure. If we want to get an arbitrarily deep tree of users, we would need to have an infinitely nested type like User[User[User[User[User[User[...]]]]]] which is of course impossible. So instead, people have a work-around using higher-kinded types, called `Fix`: case class Fix[F[_]](unfix: F[Fix[F]]) This signature may look scary, but if you apply it to User you get Fix[User](unfix: User[Fix[User]]) and all this means is that now we can deal with Fix[User] which means the same thing as User[User[...]]. You can construct one such Fix[User] differing levels like so: Fix( User( id = 1L, name = "Josh", friends = List( Fix( User( id = 2L, name = "John", friends = List( Fix( User( id = 3L, name = "Stacey" friends = List.empty ) ) ) ), Fix( User( id = 4L name = "Mary" friends = List.empty ) ) ) )

harpocrates 8y ago

Some other applications are more interesting. For instance, finger trees (which back the efficient implementations of a handful of immutable data structures) usually are implemented in a way that requires polymorphic recursion.

catnaroek 8y ago

I don't see anything wrong with rose trees: datatype 'a tree = T of 'a * 'a tree list Do you?