New primitives and combinators

[ivanperez-keera]

This space is for combinators that are not immediate/trivial, to see if others are able to come up with the solution. I consider it more of a fun space to see who comes up with the cleverest solution.

[ivanperez-keera]

How would you write a freeze combinator that takes two streams and freezes (holds) the value of the second whenever the first one is true?

[ivanperez-keera]

How would you write a time combinator that takes a boolean stream and tells you the time since it was last True? For example, applying it to the stream [True, False, True, True, False, False, False, ...] would render the stream [1, 1, 2, 1, 1, 2, 3,...].

[ivanperez-keera]

The value for the first time is disputable. I could be convinced that it would make more sense to make it 0.

[ivanperez-keera]

How would you make a changed combinator that is true whenever the value changes, and false otherwise?

[ivanperez-keera]

This one is a bit easier than the others.

[ivanperez-keera]

I've spent some time thinking about how to create a makeA :: Array n (Stream a) -> Stream (Array n a) constructor that takes the component streams and puts them together into a stream of arrays.

In theory it sounds like it should be possible to do it, but with the interface we have to work with arrays, I've only been able to do it if I can create a default value of type a (because then it's just traversing over the element streams, updating each position with the value):

makeA :: forall a n . (KnownNat n) => a -> Array n (Stream a) -> Stream (Array n a)
makeA def xs = foldl updatePos initialArray indexedElems
  where
    updatePos :: Stream (Array n a) -> (Int, Stream a) -> Stream (Array n a)
    updatePos s (i, x) = s !! i = : x

    indexedElems :: [(Int, Stream a)]
    indexedElems = zip [0..] (arrayElems xs)

    initialArray :: Stream (Array n a)
    initialArray = array (replicate n def)

I'd welcome clever ideas I have not thought of.

[ivanperez-keera]

this only works under the assumption that Copilot won't evaluate the undefined values before they're replaced with something else in (That happens to be the case in today's Copilot, but I don't know if we can rely on this always being true.)

Does that work if you compile it to C?

I wondered if Copilot should offer a primitive with that has (approximately) this type signature:

generate :: (Int -> Stream a) -> Stream (Array n a)

Hmm, I have to think about this. I don't know off the top of my head. My mind goes towards usability on the side of the user.

[RyanGlScott]

Does that work if you compile it to C?

Ah, indeed it doesn't. I only tried the interpreter, which does happen to avoid evaluating the undefined values.

[ivanperez-keera]

We could, however, create instances of a class like https://hackage.haskell.org/package/data-default-0.8.0.0/docs/Data-Default.html for all types that are Typed (except maybe structs, and even then, the function typeOf returns a constructor Struct, which contains a value of the type of the struct (the constructor Struct is odd in that sense because it's the only one containing an actual value).

Alternative incomplete implementation:

makeA :: forall a n . (Default a, KnownNat n) => Array n (Stream a) -> Stream (Array n a)
makeA xs = foldl updatePos initialArray indexedElems
  where
    updatePos :: Stream (Array n a) -> (Int, Stream a) -> Stream (Array n a)
    updatePos s (i, x) = s !! i = : x

    indexedElems :: [(Int, Stream a)]
    indexedElems = zip [0..] (arrayElems xs)

    initialArray :: Stream (Array n a)
    initialArray = array (replicate n def)
    
instance Default Bool where
  def = False
instance Default Int8 where
  def = 0
--- idem for all numeric types
instance (KnownNat n, Default a) => Default (Array n a) where
  def = ??? -- How to do this one?
instance Default (Struct a) where
  def = v
    where (Struct v) = typeOf

[ivanperez-keera]

I haven't tried it but, perhaps if we enable instance signatures, we can capture the n with forall in the explicit signature of def in the instance for Default (Array n a), and then use it in the implementation of def to replicate a default value n times.

[RyanGlScott]

Indeed, having the ability to create default values of each type would be quite handy.

except maybe structs, and even then, the function typeOf returns a constructor Struct, which contains a value of the type of the struct (the constructor Struct is odd in that sense because it's the only one containing an actual value)

Right, this is something that I've noticed as well. In #566, I worked around this quirk by filling the fields of each Struct type with undefined. That happens to work because Copilot never inspects the values of these Struct types (and thus never evaluates the undefined values), but it is a rather delicate arrangement.

If we wanted to go down this route, I think it is quite possible to replace the value in the Struct type with a Proxy:

 data Type :: * -> * where
   ...
-  Struct :: (Typed a, Struct a) => a -> Type a
+  Struct :: (Typed a, Struct a) => Proxy a -> Type a

That would allow us to avoid using undefined at all when constructing Struct types. (It's not strictly necessary for the changes you're proposing in this discussion, but it's something worth considering on its own.)

I haven't tried it but, perhaps if we enable instance signatures, we can capture the n with forall in the explicit signature of def in the instance for Default (Array n a), and then use it in the implementation of def to replicate a default value n times.

Something like this should work with just ScopedTypeVariables:

{-# LANGUAGE ScopedTypeVariables #-}

instance (KnownNat n, Default a) => Default (Array n a) where
  def = array (replicate (fromIntegral (natVal (Proxy @n))) def)

In instance declarations, the type variables from the instance head scope over the method bodies, so n will be in scope in natVal (Proxy @n).