I may have missed some.
Now, I understand that these libraries have different purposes and aprroaches, but all of them, in one way or the other, try to improve the status of collections in Nim, either by adding new data structures, providing more operations on seqs, supporting iterators or a mix of all of those.
It would be really nice if everyone could agree on a standard collection library that
I understand that it will not be possible to satisfy everyone, but at the same time it is important to standardize collections, since libraries will build on them and having standard data structures improves interoperability.
Luckily, Nim offers seqs, tables, sets and more in the standard library, so it is easy to interoperate among libraries without getting stuck with custom data structures. On the other hand, I think that the proliferation of collection libraries shows that something is still missing in the stdlib, and it would be nice to have a module that is widely recognized as the thing to import when working with collections in a more functional way.
What do people think about this?
@andrea, hi!
I think that it could be a good idea, if we'll have working concepts. We could have some concepts in the standard library, describing lists, maps, etc. and their operations.
But for now we must abide the agreement and it's sad, as the compiler can do it.
How can we describe map function with the current concepts design? This doesn't work :-(
type
Seq*[T] = concept x
proc mapF(v: T): U
x.map(mapF) is Seq[U]
echo seq[int] is Seq[int]
I was thinking about using concepts to describe elementary operations, such as
type
RandomAccess[A] = concept x
var index: int
x[index] is A
Appendable[A] = concept x
x.add(x[0])
Initializable[A] = concept x
create(type(x)) is type(x)
Iterable[A] = concept x
for y in x:
y is A
Seq[A] = concept x
x is Appendable[A]
x is Iterable[A]
x is Initializable[A]
and then use these to build the operations, but I tried and found some issues related to higher kinded types.
Still, even without formalizing the thing into concepts, it would be sufficient to have a uniform set of operations on various collections, even though there is no concept that unifies them
@vega:
I think that it could be a good idea, if we'll have working concepts. We could have some concepts in the standard library, describing lists, maps, etc. and their operations.
But for now we must abide the agreement and it's sad, as the compiler can do it.
I agree with all of this. Fortunately, under the essential for 1.0 section of the todo.txt for Nim is
- concept needs to be refined, a nice name for the feature is not enough.
so you can expect that this will receive attention sooner rather than later.
@andrea:
I was thinking about using concepts to describe elementary operations ... , but I tried and found some issues related to higher kinded types.
If you'd like to have higher kinded types in Nim, it might help if you mention your issues here. Looking at your example, it fails in the same way that @vega's does.
Also, even if the compiler isn't ready, I think it would be nice to see a formalization into concepts of a collections API, in the Nim+Concepts we wish we had, even if only in comments.
Actually my example compiles, and seq[int] is Seq[int] returns true. :-)
The issue that I have with HKT is when I try to define things like map. I would like to write (fictional syntax)
proc map[A, B, C[A] : Seq[A]](xs: C[A], f: proc(a: A): B): C[B] = ???
The problem being that I have some type constructor like seq, and I have a concrete instance like seq[A]; I would like to state the return type has the same type constructor seq, but a different inner type, hence seq[B].
I could do this if I actually had a concrete type constructor like seq[A], but I only have a type which belongs to the concept Seq[A], and I don't know how to "change its inner type from A to B while retaining the same type constructor", whatever that means.
But I think that one can improve collections without involving concepts at all. It is enough to have a consistent set of operations that work seamlessly across the collections in the stdlib (arrays, sequences, strings, sets, bitsets, maps, strmaps, iterators, lists). Not all operations make sense on all collections, but many do. For instance, arrays will not have filter, because the target size is unkwown, but can have map.
Having the design formalized through concepts would be a plus, but I think can be postponed.
I consider the concept implementation to be seriously broken. In particular generic parametrization (via [T]) does not work with concepts. (Hint: That it compiles, doesn't mean that it works ;-) ) I have an alternative implementation though (and spec) that lowers concepts to ordinary generic procs that act as type predicates. Still lots of work ahead to get it into shape, but my first tests were a success.
It is enough to have a consistent set of operations
Agreed and http://nim-lang.org/docs/apis.html was my first attempt on this. This document is hardly known though.
@andrea
When I compile your example with Nim(devel) it returns false, both on Linux and OS X. Could you describe your setup?
While I agree that having a consistent API for collections would be nice, I think having the API expressed as concepts is more than just a slight plus. However, there's no need to wait, just design as though the desired concept capability is there.
Sorry, I forgot tdo define
proc create[A](x: typedesc[seq[A]]): seq[A] = @[]
In order to define how to create new collections, I needed a uniform api to create an empty one, so that
create(seq[int])
works. With that definition in scope, seq[int] is Seq[int] should be true
Following is a shot in the dark. I'm not sure it is possible to make it work, let alone play nice with type inference (I don't have any experience with Nim's type system and concepts). The whole thing seems to be inherently cubersome, too.
@andrea
The problem being that I have some type constructor like seq, and I have a concrete instance like seq[A]; I would like to state the return type has the same type constructor seq, but a different inner type, hence seq[B]
Here's an idea, inspired by the way type inference is implemented in nimfp's for comprehensions: since we don't have a language-level feature that would allow us to abstract over type constructors, why don't we emulate it with concepts and conventions? Since we can write templates that operate on typedescs, and use their results as types, why not define something along the lines of this (not working code):
type
# `a` is constructor's type parameter. Since we can only define concept
# for concrete types, the concept is parameterized.
Constructor1[a] = concept k
# These procs would have to be defined for each instance.
# They don't need to have a body - they are only used for their types.
# since we don't have representation for type constructors,
# we can only describe transformations between concrete instances
constructor1Replace(k, 1) # should compile
constructor1Unapply(k) # should compile
# laws to make sure procs function as expected
# typeEq is a template that checks types for equality
# again, not sure how to make it work inside concept declaration
typeEq(type(constructor1Unapply(k)), a) # `k` should contain information about type parameter
typeEq(type(constructor1Replace(k, a)), k) # replacing type parameter with `a` should give the same type
# replace should change unapply's result
typeEq(type(constructor1Unapply(constructor1Replace(k, 1))), int)
typeEq(type(constructor1Unapply(constructor1Replace(k, ""))), string)
# We can use Constructor1 to define Seq
Seq[a] = concept sa
sa is Constructor1[a]
# we can now express map contract
# This can't possibly cover all cases, but at least it's something
map(sa, proc (a): int) is type(constructor1Replace(sa, 1))
map(sa, proc (a): string) is type(constructor1Replace(sa, ""))
# Assuming we have identity function
map(sa, identity) is sa
# Constructor1 instance for seq
# procs are only used to connect types, no implementation is necessary
proc constructor1Unapply[A](s: seq[A]): A = discard
proc constructor1Replace[A, B](s: seq[A], b: B): seq[B] = discard
I fiddled with Constructor1 definition a bit, but failed to make it compile and work; maybe someone here will have better luck.
UPD. I had mistakenly used templates and typedescs in the first version of this message. Fixed the code now.