Higher order function which outputs Option of multiple generics - Cannot instantiate

[mratsim]

I am trying to implement unfoldr from Haskell

This test case works fine, please note the Òption[(T, T)]

from options import Option, isSome, get, none, some
proc unfoldr*[T, U](f: proc(items: T): Option[(T, T)], x:U): seq[T] {. inline .}=
    ## Build a sequence from function f: T -> Option(T,T) and a seed of type T
    result = @[]
    var a: U = x
    var b: T
    var fa = f(a)

    while fa.isSome():
        (b, a) = fa.get()
        result.add(b)
        fa = f(a)

proc divmod10(n: int): Option[(int, int)] =
    if n == 0:
        return none((int,int))
    return some(( (n mod 10).int(), n div 10))

proc toDigits*(n: int): seq[int] =
    unfoldr(divmod10,n)

echo toDigits(123456) # @[6, 5, 4, 3, 2, 1]

However unfoldr type signature should be (in Haskell)

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

Changing it in the code to the following gives me an error:

proc unfoldr*[T, U](f: proc(items: T): Option[(T, U)], x:U): seq[T] {. inline .}=

unfold.nim(4, 46) Error: cannot instantiate Option
got: ((typedesc[T], U))
but expected: (T)

From the error, I would guess that in the second case the whole Option[(T, U)] got matched by T instead of being unpacked

[mratsim]

CC-ing @nigredo-tori

[mratsim]

Here is a test case with different T, U types using fibonacci sequence.
It should compile once the issue is fixed.

import options
import future
import sequtils

proc unfoldrIter[T, U](f: T -> Option[(T, U)], x:U): iterator():T =
    result = iterator(): T {.closure.}=
        var a: U = x
        var b: T
        var fa = f(a)

        while fa.isSome():
            (b, a) = fa.get()
            yield b
            fa = f(a)

proc takeWhile*[T](iter: iterator(): T, cond: proc(x: T):bool): iterator(): T =
  result = iterator(): T {.closure.}=
    var r = iter()
    while not finished(iter) and cond(r):
      yield r
      r = iter()

######  Get power of 2 below 100000
# Works fine today with Option[(T, T)] signature
proc pow2(x: int): Option[(int,int)] = some((x, x*2))

var power_generator = unfoldrIter(pow2, 1).takeWhile(x => x< 100_000)
echo power_generator().toseq # @[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]


# Get Fibonacci sequence below 100000
# Should work after fix
proc fib( a, b: int ): Option[(int, (int,int))] =
    some((a+b, (b, a+b))

# var fib_generator = unfoldrIter(fib, (0,1)).takeWhile(x => x< 100_000)
# echo fib_generator().toseq

[nigredo-tori]

Seems like a duplicate of #4061

[mratsim]

From #4061 I managed to get the first example to compile by naming the tuple fields

import options
import future
import sequtils

proc unfoldr[T, U](f: T -> Option[tuple[item: T, seed: U]], x:U): seq[T] {. inline .}=
    ## Build a sequence T from function f: T -> Option(T,U) and a seed of type U
    result = @[]
    var a: U = x
    var b: T
    var fa = f(a)

    while fa.isSome():
        (b, a) = fa.get()
        result.add(b)
        fa = f(a)

###### 1. Get the digits from a number
proc divmod10(n: int): Option[(int, int)] =
    if n == 0:
        return none((int,int))
    return some(( (n mod 10).int(), n div 10))

proc toDigits*(n: int): seq[int] =
    unfoldr(divmod10,n)

proc reverse[T](xs: openarray[T]): seq[T] =
  ## Reverse a sequence or array and output a sequence
  result = newSeq[T](xs.len)
  for i, x in xs:
    result[^i-1] = x

echo "Unfolding 123456 digits"
echo toDigits(123456).reverse # @[1, 2, 3, 4, 5, 6]

Second example as well

import options
import future
import sequtils

proc unfoldrIter[T, U](f: T -> Option[tuple[item: T, seed: U]], x:U): iterator():T =
    ## Build an iterator T from function f: T -> Option(T,U) and a seed of type U
    ## Useful to produce an infinite generator like list of power of 2 or fibonacci
    result = iterator(): T {.closure.}=
        var a: U = x
        var b: T
        var fa = f(a)

        while fa.isSome():
            (b, a) = fa.get()
            yield b
            fa = f(a)

###### Get powers of 2 below 100000
proc takeWhile*[T](iter: iterator(): T, cond: proc(x: T):bool): iterator(): T =
  result = iterator(): T {.closure.}=
    var r = iter()
    while not finished(iter) and cond(r):
      yield r
      r = iter()

proc pow2(x: int): Option[(int,int)] = some((x, x*2))

echo "Unfolding powers of 2 below 100 000"
var power_generator = unfoldrIter(pow2, 2).takeWhile(x => x< 100_000)
echo power_generator().toseq # @[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]

But the third example (fibonacci) with T: int and U: (int, int) doesn't compile. It seems to be due to tuple unpacking inside Option/custom types. Sorry it's kind of a huge dump. I can open a new issue "tuple unpacking inside Option/custom type" if the rootcause is different from the "Cannot Instantiate" issue

import options
import future
import sequtils

proc unfoldrIter[T, U](f: T -> Option[tuple[item: T, seed: U]], x:U): iterator():T =
    ## Build an iterator from function f: T -> Option(T,T) and a seed of type T
    ## Useful to produce an infinite generator like list of power of 2 or fibonacci
    result = iterator(): T {.closure.}=
        var a: U = x
        var b: T
        var fa = f(a)

        while fa.isSome():
            (b, a) = fa.get()
            yield b
            fa = f(a)

###### Tuple and options type matching function
# Works as stand alone
proc foo(x: tuple[a, b: int]): tuple[x:int, y:int] =
    return (x.a, x.b)

# Works as stand alone
proc foo2(x: tuple[a, b: int]): (int, int) =
    return (x.a, x.b)

# Works as stand alone
proc foo3(x: tuple[a, b: int]): (int, (int, int)) =
    return (x.a, (x.b, x.a ))

# Works as stand alone
proc fibonacci(x: tuple[a, b: int]): tuple[x:int, y: tuple[b, apb: int]] =
    return (x.a + x.b, (x.b, x.a + x.b))

# Does not work
proc bar((a,b): (int, int)): (int, (int,int)) =
   return (a + b, (b, a + b))
# Error: ')' expected - after "proc bar("

# Does not work
proc baz(x: tuple[a, b: int]): Option[tuple[x:int, y: tuple[b, apb: int]]] =
    return some(
               (x.a + x.b, (x.b, x.a + x.b))
                )
#Error: type mismatch: got (Option[(int, (int, int))]) but expected 'Option[tuple[x: int, y: tuple[b: int, apb: int]]]'

###
### Now testing the functions also as input to unfoldrIter
###

# Works as stand alone
proc fizz(x: tuple[a, b: int]): Option[(int, (int, int))] =
    return some(
                (x.a + x.b, (x.b, x.a + x.b))
                )
# Now Nim compiles the proc but errors if called by unfoldIter
# Error: type mismatch: got (proc (x: tuple[a: int, b: int]): Option[(int, (int, int))]{.noSideEffect, gcsafe, locks: 0.}, (int, int))
# but expected one of:
# proc unfoldrIter[T, U](f: T -> Option[tuple[item: T, seed: U]]; x: U): iterator (): T

# Works as stand alone
proc bazz(x: tuple[a, b: int]): auto =
    return some(
                (x.a + x.b, (x.b, x.a + x.b))
                )
# Nim also compiles the proc but errors with same type signature
# Error: type mismatch: got (proc (x: tuple[a: int, b: int]): Option[(int, (int, int))]{.noSideEffect, gcsafe, locks: 0.}, (int, int))
# but expected one of:
# proc unfoldrIter[T, U](f: T -> Option[tuple[item: T, seed: U]]; x: U): iterator (): T

## Test if different [T, U] type within Option type can be called
echo "Unfolding power fibonacci numbers below 100 000"
var fibonacci_generator = unfoldrIter(fib, (0,1)).takeWhile(x => x< 100_000)
echo fibonacci_generator().toseq

From the last 2 errors, I believe unfoldrIter(fizzbuzz, (0,1)) does not work because I had to use named field items and seed in the unfoldrIter definition. If original issue is fixed, I wouldn't and the fizz and the buzz function would probably work as intended

[nigredo-tori]

Error: ')' expected - after "proc bar("

Proc arguments don't support destructuring syntax - you need an assignment for that:

proc bar(t: (int, int)): (int, (int,int)) =
   let (a, b) = t
   return (a + b, (b, a + b))

Error: type mismatch: got (Option[(int, (int, int))]) but expected 'Option[tuple[x: int, y: tuple[b: int, apb: int]]]'

Inference for tuples doesn't seem to work here, sadly. Explicit ascriptions do the trick, as usual:

return some((x: x.a + x.b, y: (b: x.b, apb: x.a + x.b)))

Error: type mismatch: got (proc (x: tuple[a: int, b: int]): Option[(int, (int, int))]{.noSideEffect, gcsafe, locks: 0.}, (int, int))
but expected one of:
proc unfoldrIter[T, U](f: T -> Option[tuple[item: T, seed: U]]; x: U): iterator (): T

That's because your unfoldrIter signature is incorrect: it should be

proc unfoldrIter[T, U](f: U -> Option[tuple[item: T, seed: U]], x:U): iterator():T =

This also fixes the next error.

The final example also works with fib defined like this:

proc fib(t: (int, int)): Option[(int, (int, int))] =
  let (a, b) = t
  some((a+b, (b, a+b)))

[AjBreidenbach]

Is the same true for objects?

I got the following error trying to wrap jQuery

main.nim(10, 6) Error: type mismatch: got (string, proc (e: Event){.noSideEffect, gcsafe, locks: 0.})
but expected one of: 
proc click(s1: cstring; c1: proc (e: Event))
proc click(e: Element)

Maybe I just did something stupid, but the solution doesn't seem obvious to me

This is the import for click

proc click(w: Window = window, selector: cstring, onClick: proc(e: Event))

This is my ergonomic wrapper

proc click*(s1: cstring, c1: proc(e: Event)) =
  click(selector = s1, onClick = c1)

Event type declaration

type
  Event = ref object     
  ¦ currentTarget* {.importc.}: Element
  ¦ data* {.importc.}: cstring
  ¦ metaKey* {.importc.}: cstring
  ¦ namespace* {.importc.}: cstring
  ¦ pageX* {.importc.}: cint
  ¦ pageY* {.importc.}: cint
  ¦ relatedTarget* {.importc.}: Element
  ¦ target* {.importc.}: Element
  ¦ timeStamp* {.importc.}: cint
  ¦ which* {.importc.}: cstring

Again everything works until I try to use it

proc goodbye(e: Event) =
  log("bye")
  
proc onLoad() {.exportc.} =
  "p".click(goodbye)     

Thanks in advance :)

[nigredo-tori]

@AjBreidenbach , your case has nothing to do with this issue. Your problem is that you don't export your Event type. Then in main.nim you define goodbye, which takes a parameter of type Event. I'm guessing you import dom, so this is where another Event comes from. This is what the error message really means (foo here is your module):

main.nim(10, 6) Error: type mismatch: got (string, proc (e: dom.Event){.noSideEffect, gcsafe, locks: 0.})
but expected one of: 
proc click(s1: cstring; c1: proc (e: foo.Event))
proc click(e: dom.Element)

A quick fix would be to export your Event, and define goodbye like this:

proc goodbye(e: foo.Event) =

However I recommend renaming Event to something like JQueryEvent to disambiguate, since you will often use dom and jquery in the same module.

[AjBreidenbach]

Hey sorry about that. Thanks for the help! I had a feeling I did something fucky :D

[andreaferretti]

Let me recap, because here there are many issues conflated.

I see three Nim limitations:

• type inference can infer the types of field in tuples only with explicit field names
• proc arguments don't support destructuring syntax
• inferring the return type work well for nested tuples, but not wrapped in options ((Option[(int, (int, int))]) but expected 'Option[tuple[x: int, y: tuple[b: int, apb: int]]]')

Then there are a few issues in example code:

• in @mratsim examples, the signature of unfoldIter is incorrect
• @AjBreidenbach has an unrelated error, with a fix by @nigredo-tori

I think that's all.

Is any of the first three something that Nim ought to support? If so, maybe we can open more specific issues and close this one

[narimiran]

Is any of the first three something that Nim ought to support? If so, maybe we can open more specific issues and close this one

Can we close this one, then?

[metagn]

Now the (T, U) examples give:

Error: Mixing types and values in tuples is not allowed.