Mirror of forum.nim-lang.org

2654 :: Using concepts for generic structures

• komerdoor (orginal) [2016-12-08T18:34:10+01:00] view original

  I want to do the following in a generic way:

  type
    Identity[T] = object
      value: T
  
  # For testing: 'int' acts as monoid under addition
  proc `&`(a: int, b: int): int =
    a + b
  
  proc `$`[T](a: Identity[T]): string =
    $a.value
  
  proc `==`[T](a: Identity[T], b: Identity[T]): bool =
    a.value == b.value
  
  proc `&`[T](a: Identity[T], b: Identity[T]): Identity[T] =
    Identity[T](value: a.value & b.value)
  
  proc identity[T](a: Identity[T]): Identity[T] =
    Identity[T](value: 0) # For testing: forced as identity for 'int' under addition
  
  let ca = Identity[int](value: 3)
  let cb = Identity[int](value: 6)
  let cc = Identity[int](value: 6)
  
  echo("Setoid compare: ", cb == cc)
  echo("Monoid identity: ", identity(ca))
  echo("Semigroup append (=9): ", ca & cb)
  Run

  I tried the following:

  type
    Setoid[T] = concept a, b
      a.value is T
      a == b is bool
    
    Semigroup[T] = concept a, b
      a.value is T
      a & b is Semigroup[T]
    
    Monoid[T] = concept a of Semigroup[T]
      identity(a) is Monoid[T]
    
    Identity[T] = object
      value: T
  
  # For testing: 'int' acts as monoid under addition
  proc `&`(a: int, b: int): int =
    a + b
  
  proc `$`[T](a: Identity[T]): string =
    $a.value
  
  proc `==`(a: Setoid, b: Setoid): bool =
    echo "Compared" # For testing
    a.value == b.value
  
  proc `&`[T](a: Semigroup[T], b: Semigroup[T]): Semigroup[T] =
    Semigroup[T](value: a.value & b.value)
  
  proc identity[T](a: Monoid[T]): Monoid[T] =
    Monoid[T](value: 0) # For testing: forced as identity for 'int' under addition
  
  let ca = Identity[int](value: 3)
  let cb = Identity[int](value: 6)
  let cc = Identity[int](value: 6)
  
  echo("Setoid compare: ", cb == cc)
  echo("Monoid identity: ", identity(ca))
  echo("Semigroup append (=9): ", ca & cb)
  Run

  But can only get the "Setoid compare" to work :( . I am sure I am doing something stupid. But what?

  Edit: Renamed Constant to Identity as Constant may never change once assigned

---

• pdv (orginal) [2016-12-09T18:45:24+01:00] view original

  A couple of notes:

  1. &, == etc are likely to be heavily overloaded by code that knows nothing about laws you imply. For example, a & identity(type(a)) === a' might not hold for some container type with referential equality - but it still would be a `Monoid by your condition. In concepts it's generally better to use some names that are unlikely to be unintentionally overriden, preferably ones that match corresponding entities in other languages/libraries (e.g. mappend instead of &). More convenient aliases can be implemented as generic wrappers.
  2. Parameterized concepts (like type Container[A] = concept ...) are not properly supported at the moment (there is an ongoing effort to implement those). Even if they were, I personally do not think that inferring a parameter without some additional information would be possible. Fortunately, parameterized concepts are not required in this example.
  3. Concepts are type classes, rather than actual types. This means that this code:

  proc `&`(a: Semigroup, b: Semigroup): Semigroup
    
  Run

  is more or less the same as this:

  proc `&`[A: Semigroup, B: Semigroup, C: Semigroup](a: A, b: B): C
    
  Run

  So a and b can have different types, and C can't even be inferred (so this won't compile). Type-safe append operator for all semigroups would actually look like this:

  proc `&`[T: Semigroup](a: T, b: T): T
    
  Run

  Here's a working piece of code that (I think) does what you want it to:

  type
    # There's no point in making concepts generic -
    # and it doesn't really work yet, AFAIK.
    Setoid = concept a, b
      a == b is bool
    
    Semigroup = concept a, b
      a & b is type(a)
    
    Monoid = concept a
      a is Semigroup
      identity(type(a)) is type(a)
    
    Identity[T] = object
      value: T
  
  # Instances for simple types
  
  proc `&`(a, b: int): int =
    a + b
  # Changed the argument to a `typedesc` - we don't use the value anyway
  proc identity(t = int): int = 0
  # Same as this:
  # proc identity(t: typedesc[int]): int = 0
  
  assert: int is Setoid
  assert: int is Semigroup
  assert: int is Monoid
  
  assert: string is Setoid
  # We've got `&` for free
  assert: string is Semigroup
  # No `identity`
  assert: string isNot Monoid
  
  assert: float is Setoid
  assert: float isNot Semigroup
  assert: float isNot Monoid
  
  # Instances for Identity
  proc `==`[T: Setoid](a, b: Identity[T]): bool =
    a.value == b.value
  
  # Only defined if the underlying type itself is a Semigroup
  proc `&`[T: Semigroup](a, b: Identity[T]): Identity[T] =
    Identity[T](value: a.value & b.value)
  
  proc identity[T: Monoid](t:typedesc[Identity[T]]): Identity[T] =
    Identity[T](value: identity(T))
  
  assert: Identity[int] is Setoid
  assert: Identity[int] is Semigroup
  assert: Identity[int] is Monoid
  
  assert: Identity[string] is Setoid
  assert: Identity[string] is Semigroup
  assert: Identity[string] isNot Monoid
  
  assert: Identity[float] is Setoid
  assert: Identity[float] isNot Semigroup
  assert: Identity[float] isNot Monoid
  
  let ca = Identity[int](value: 3)
  let cb = Identity[int](value: 6)
  let cc = Identity[int](value: 6)
  
  echo("Setoid compare: ", cb == cc)
  echo("Monoid identity: ", identity(Identity[int]))
  echo("Semigroup append (=9): ", ca & cb)
  Run

  Also, you might want to take a look at emmy, specifically structures module

---

• komerdoor (orginal) [2016-12-10T16:39:12+01:00] view original

  Tnx. I read the document generics.txt before I started using the concept keyword.

  Somehow I was under the impression concepts could be parameterized for me to refer to the contained value. Of course a container type may not even have value (it could be a function type or have a pair of values [if not a tuple]) while still being valid according to what I want.

  It would have been nice if I could do T & T or T is Semigroup because then concept does not need to know about the structure of the contained types.

  Emmy looks interesting. It seems to extend the basic number types to be monoids under addition and multiplication (which they are). I already created NumberSum, NumberProduct, LogicalOr and LogicalAnd whose values are then under the their respective operation.

  I like how Emmy uses zero and id to denote identity for addition and multiplication. In a C library I wrote I called it sum_identity and product_identity. I would like something like zero, one or id, half, double to be standard.

---