instance Applicative Pattern does not respect law pure id <*> v = v

[jwaldmann]

(this was remarked by a participant of the hackathon)

The Law https://hackage.haskell.org/package/base-4.10.0.0/docs/Control-Applicative.html says that

pure id <*> v = v

but we have, e.g.,

*Sound.Tidal.Context> pure id <*> s "x y"
fromList [(s,x)] 0 1

*Sound.Tidal.Context> s "x y"
fromList [(s,x)] 0 1/2
 fromList [(s,y)] 1/2 1

[bgold-cosmos]

This stems from the "structure comes from the left" behavior, and I'm having trouble thinking of a clean way to resolve it (that doesn't break a lot of existing stuff).

Patterns fail the composition and interchange laws as well, for the same reason. Homomorphism is actually OK, because all arguments there are created with pure.

[vivid-synth]

Yeah, this has been an issue for a long time. It's not good that this is broken but I don't really see a way to fix it. Arguably the best thing to do is just to make a different typeclass, not called Applicative, and use that instead (since there is "a definition," it's just not a legal Applicative)

Btw if we do go that route, it would be great to formalize what, in fact, the behavior is!

[bgold-cosmos]

Is it Data.Functor.Apply? (with an additional pure-like function that isn't actually pure?) Apparently that's a "strong lax semi-monoidal endofunctor", and in this context I don't think I understand any of those words.

[vivid-synth]

Yeah, that is not a very approachable definition haha

I don't think Data.Functor.Apply helps us, because e.g. |*|, which is defined in terms of <$> and <*>, is not associative.

Here's an example:

d1 $ s "sn*4" (speed "2" |*| n "1 2 3 4")
-- This should, I believe, sound the same - but it doesn't:
d1 $ (s "sn*4" |*| speed "2") |*| n "1 2 3 4"

By contrast, these are equal:

[(*10),(*20)] <*>  ([(*2),(*3)] <*> [3,4])
(pure (.) <*> [(*10),(*20)] <*>  [(*2),(*3)]) <*> [3,4]

This is admittedly not the nicest counter-example, because of the pure at the beginning. I'm taking the definition from the "Composition" law defined here:

https://wiki.haskell.org/Typeclassopedia#Applicative

[yaxu]

In what other ways could we specify where structure comes from? I feel like we're missing an elegant solution here..

[bgold-cosmos]

@vivid-synth : If I understand Apply (not sure I do), I think we'd redefine operators in terms of <.> instead of <*>, and I think the similar law there:

(.) <$> u <.> v <.> w = u <.> (v <.> w)

does hold for Patterns. OTOH, I think semimonoids are supposed to have associativity for the binary operator, so I think Patterns will still fail that. On the third hand, I don't see how the laws for Data.Functor.Apply actually require associativity. Only thing I'm sure of is that I don't understand much of this.

@yaxu : I think the immediate "problem" of pure id <*> v = v could be solved by saying structure comes from the right, but I'm fairly sure other laws would still have problems - I think the deeper issue is in having the structure "come from" anywhere. I think for Patterns to be proper Applicative Functors, the structure of a |*| (b |*| c), (a |*| b) |*| c, and (b |*| a) |*| c should all be the same, and even if that's possible I'm not sure it'd be what anyone actually wants.

[telephon]

a |*| (b |*| c), (a |*| b) |*| c, and (b |*| a) |*| c should all be the same,

the case (b |*| a) |*| c wouldn't have to be the same, would it? This would require |*| to be commutative.

At first sight, it seems not so bad to have a |*| (b |*| c) = (a |*| b) |*| c. What would be a counterexample? Maybe a pattern that changes the way that structure is interpreted?

[bgold-cosmos]

You're right, I'm confusing commutativity with the interchange law.

The counterexample to associativity would be how Tidal currently works! These two are not the same:

*Sound.Tidal.Context> n "1 2" |*| (n "4" |*| n "5 6")
fromList [(n,20)] 0 1/2
 fromList [(n,40)] 1/2 1

*Sound.Tidal.Context> (n "1 2" |*| n "4") |*| n "5 6"
fromList [(n,20)] 0 1/2
 fromList [(n,48)] 1/2 1

[telephon]

this is a little confusing indeed. Is it useful?

[bgold-cosmos]

I don't know about useful, but I'm not 100% sure how to even define a behavior that guarantees associativity. I think it's easiest if structure comes from both sides in some kind of symmetric way*, but even that gets a bit odd to define for things like "0 1" + (0.25 ~> "2 3"). I think you're forced into a rule like "combination has the largest common substructure", for example "0 1" + (0.25 ~> "2 3") = "3 2 3 4"...

(*) I can't think of a structure rule that's associative but not commutative, but something probably exists

In the end, I don't think such a thing is desirable - users want to specify a beat or pattern of notes and have it go through unmodified if (for example) it's on the left. But that means giving up the idea that Patterns are strictly Applicative Functors. They're something else that I'm not sure Haskell has a name for.

[yaxu]

Perhaps ordinarily "0 1" + "1 2 3" should give neither "1 3" or "1 2 4" but "[1 3, 1 2 4]" to get existing behaviour you'd stick one pattern 'above' the other like (layer 1 "0 1") + "1 2 3" Then by default sound parameters would be on a higher layer than other parameters and then we could easily make e.g. <+ where the left hand side is placed 'above' the other and therefore define the structure (as now)

[telephon]

in APL and SuperCollider similar distinctions are done by adverbs.

// in terms of arrays:
[0, 1] + [1, 2, 3]  => [ 1, 3, 3 ]
[0, 1] +.s [1, 2, 3] => [1, 3]
[0, 1] +.x [1, 2, 3] => [ 1, 2, 3, 2, 3, 4 ]

// operator depth:
[0, 1] +.1 [1, 2, 3] => [ [ 1, 2, 3 ], [ 2, 3, 4 ] ]
[0, 1] +.-1 [1, 2, 3] => [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ] ]

// they are associative:
(([0, 1] +.x [1, 2, 3]) +.x [3, 4]) == ([0, 1] +.x ([1, 2, 3] +.x [3, 4]))

These specific ones might be useless in tidal, but at least they show a possibility, perhaps.

[yaxu]

Interesting, reminds me of Haskell's ZipList type which just exists to indicate different behaviour when combining lists.

I think the options are limited with Tidal. In my mind it comes down to combining patterns by lining them on top of each other and looking down on them. The upper ones give the structure. If you try to put two patterns on the same level you get a mess.

[telephon]

In my mind it comes down to combining patterns by lining them on top of each other and looking down on them.

This makes sense. But this should be associative, shouldn't it?

[vivid-synth]

In my mind it comes down to combining patterns by lining them on top of each other and looking down on them. The upper ones give the structure.

This is a really interesting way of looking at it that I hadn't thought of. A <+-ish operator which defines "where the structure is" is intriguing.

[yaxu]

Ok adding 'layer' sounds like a good way forward then:

data Pattern a = Pattern {arc :: Arc -> [Event a], layer :: Layer}
  deriving Typeable

I don't know whether layer should be relative or absolute, e.g.:

data Layer = Above | Below | Same

or

type Layer = Int

Probably the latter, otherwise I think we'd still have the same problem with associativity.

We could then steal the > and < operators, a bold move but basically all the arrow-like operators are taken in Haskell and less than / greater than isn't something you use a lot in tidal at the moment.

Then these pairs would be equivalent:

d1 $ s "bd sn" < n "0 1 2"
d1 $ s "bd sn" # n "0 1 2"

d1 $ s "bd sn" > n "0 1 2"
d1 $ n "0 1 2" # s "bd sn"

d1 $ s "bd sn" > n "0 1 2" <+ n"<4 8>" 
d1 $ n "0 1 2" # s "bd sn" |+| n "<4 8>"

Make sense?

[jwaldmann]

I think you're forced into a rule like "combination has the largest common substructure"

Yes. Pattern p describes a periodic infinite sequence. For simplicity, assume Pattern a=[a] (all parts take unit time). Then the semantics of p :: Pattern a is cycle p, e.g.,

take 10 $ cycle "foo"   ==>  "foofoofoof"

Then the ZipList Applicative instance is again cyclic, and the period length of p <*> q is lcm (length p) (length q).

take 10 $ getZipList $ (ZipList $ cycle [id,succ]) <*> (ZipList $ cycle "foo")

==> "fpogopfpog"

(period of result is 6). This should nicely fulfil all the laws (where pure x = cycle [x], as it is for ZipList)

Does Tidal have such an operator?

[yaxu]

But Pattern a is not a list of a, but a function of a, over rational time.

Tidal used to be based on lists, and store a period, with use of lcm when combining, but I much prefer the current approach to time which is more flexible in many cases.

[bgold-cosmos]

There's nothing in the formal specification of Patterns that says anything about periodicity. rand is not periodic (well, technically it has a period of 2^32 or something), and it's trivial to define a pattern such as Pattern $ \(s,e) -> [((s,e), (s,e), (floor s))] which never repeats (even in an infinite limit).

For patterns that are periodic it's possible in many cases to deduce the period of combinations using lcm or similar. But I'm not sure that computing the period is even formally decidable if we're given the ability to write arbitrarily complex pattern combinators.

[yaxu]

Just returning to this, howabout 'structure comes from the smallest elements'? so "[1 2] 3" + "4 [5 6]" would give "[5 6] [8 9]"?

[dktr0]

I can imagine a lot of circumstances where that behaviour would be useful, but I can also imagine circumstances where it would be less useful. Sometimes it is desirable to "sub sample" the pattern on the right, while other times you no doubt want a combination where every discrete event in both patterns is preserved. I think my main thought about this would be that maybe Tidal doesn't need to prescribe a method of combination? We just need different operators for the two cases (perhaps there are three cases - in you include one where the structure comes from the right) and clear explanations of when to use which one.

[dktr0]

Thinking out loud... (<+) -- structure from the left (+>) -- structure from the right (<+>) -- addition of values with preservation of both structures

[dktr0]

I realize you need a "default" behaviour for when a pure operation is lifted into Pattern - but that little piece of software trivia need not deflect anything that affects downstream users / use in performance / on the surface. The default behaviour (eg. for liftA2, >>=) could be any of the three cases. But then in practice, in live coding with Tidal, we might define (in addition to the explicit operations like the one in the comment above) our own lifting operators that are similarly explicit about how the structures are combined. liftL liftR liftBoth... no immediate ideas for what good operator equivalents might be.

[yaxu]

Yes sounds good, I think there could be a few potentially useful ways to do <+> to seek out.

One problem is that <- and -> would be the equivalent for subtraction, but these operators are already taken in haskell.

I'm toying with a potential rewrite here: https://github.com/yaxu/Tidalish/tree/master/Sound/Tidal

There are <* and *> for taking structure from the left or right, and <*> as an attempt at taking structure from the smaller ones

It also renames arc to span, and getting events works a bit differently.. Instead of getting events that are active during the timespan you give, you get the part of the event that's active during the span. So if you ask for half a cycle, and there's an event there that lasts the whole cycle, you'll only get half of it. I think this will be a cleaner approach.

[dktr0]

I think pretty much all of the angle bracket + arithmetic operators have a standard meaning in some more or less standard Haskell module... And (notwithstanding what I implied above about not letting backend considerations deflect user/performer experience...) it seems a shame to lose the standard meaning of <*> still. What about running with # for these combinators, since it is already familiar to many TidalCyclers? So:

- -- from the left

-# -- from the right

-# -- from both

=# -- from both

-- synonym for #=

[dktr0]

(Apparently my last line there triggered some markdown notation! I was saying "#" could be a synonym for #=#)

[yaxu]

By standard meaning of <*> do you mean the haskell standard, or the current tidal standard? The problem is that the current tidal version doesn't conform to the standard applicative laws. This new version is trying to better conform to those laws and so be more standard, but to be honest I don't fully understand them..

[yaxu]

I think I'd like to keep # as shorthand for |=|, i.e. for replacing values inside patterns of parameters. but then we could have <=| (or <# as shorthand) for taking structure from the left, and |=> (or #>) for taking structure from the right as well as values.

[bgold-cosmos]

In "structure comes from the smallest elements", what about these cases?

"0 1 2" + "3 4" = ? Is it "3 4 6" or "3 [4 5] 6" or something else?

"[0, 1 2]" + "[3 4, 5]" = ? Since patterns can contain multiple overlapping events I'm not sure if there's always a clear "smallest".

And as I think @yaxu is alluding to in the last comment, I think it may be worthwhile to make a distinction in behavior between operators like + on patterns of numerical types, and operators like # on ParamPatterns. For things like n "c e g a" # s "supersaw" having a clear "structure from the left" behavior is very nice. For "0 1 2" +"3 4" maybe less so.

[yaxu]

That'd be "3 4 6" Currently as I envisage it, it'd first work one way - matching the onsets on the right that fit inside the spans on the left. It takes the structure from the right, but filters out events on the right that are longer than their matched events on the left (in this case, filtering out all of them). Then it does the opposite (i.e., doing the same but with left and right swapped), and concatenates the two lists.

[yaxu]

Something like "3 [4 5] 6" would be nice as an option though, if we can come up with an algorithm for that!

[yaxu]

@bgold-cosmos + yes agreed on distinction between + and |+| etc, although I think with |/| and / you don't want the 'structure to come from the left', because / isn't commutative, so order is already taken..

[dktr0]

It seems to me that (1) "different ways of combining structures" and (2) "conforming to Haskell laws for Applicative" are probably issues it is helpful to keep rather separate.

1. In terms of different ways of combining structures, musical utility is probably maximized when you have lots of different combinators and the way they behave is clearly documented. And that's it. In this problem space, then, there is no a priori way of deducing a correct behaviour from an arithmetic precedent or a Haskell law. (Concretely: one could certainly have some combinator that divides and takes the structure from the left - because there's no reason not to and it's exactly what might be most expressive in some circumstance. Division is entirely about the value not the structure.)

2. My understanding of the Applicative laws is shaky to say the least too... However, my instinct is that they are mostly about making sure that (for example) liftA2 (+) "0 1 2" "3 4" gives exactly the same result as liftA2 (+) "3 4" "0 1 2" (ie. result in terms of structure not value, although in the specific case of + it, coincidentally, also gives the same value). Clearly this criterion is not met if you go with either the left or the right as the only source of structure, nor is it met in any variant where some aspect of the structure comes from the left while some other aspect of the structure comes from the right.

I think the "3 [4 5] 6" interpretation is viable for Applicative and also quite musically intuitive. Combining two rhythms by layering them and appreciating the new polyrhythmic rhythm thus created is a super-common feature of many musical cultures!!! I believe we would find quite a few people's musical intuitions are surprised when they collide with the fact of this not being quite the "default" behaviour in many Tidal "idioms".

At first glance the algorithm for this particular case (combining two patterns of discrete events) seems straightforward: Wherever there is an onset in either pattern, there is an onset in the combined pattern, with spans adjusted to the pattern of onsets. Then at each "location" in the resulting structure, each of the input structures are sampled with the sampled values provided to the binary function argument of liftA2 (the + in our example).

Note: It seems to me that this "poly-rhythm" interpretation actually is a kind of "smallest structure in a given window" interpretation and that it is rather analogous to the interpretation of lists as non-deterministic computations in "general Haskell", in the way that the number of events in the resulting pattern increases as a non-linear function of the number of events in the input patterns.

(Conversely: simply comparing patterns to decide which one is most detailed (smallest) doesn't sound right (I don't think this is being suggested by anyone - I am just thinking out loud.) Is sine more detailed or less detailed than [1 2 3 4]? I realize in the current Tidal implementation sine leads to one item in the list which might seem like "less detailed" but... that is merely an implementation detail. Conceptually a sine wave that has yet to be sampled seems both more and less detailed than [1 2 3 4] to me.)

Returning to some of the cases in comments above where "structure coming from the left" was deemed desirable: certainly that should be supported - by "custom" combinators - but I believe it has nothing to do with conforming to the Applicative laws and probably inherently contradicts them. That's no problem though - if you want # to take structure from the left, you can go ahead and define it that way! You just wouldn't be able to define it as a straightforward lifting of a pure function into the Pattern context, while also obeying the laws, but that's no problem, since the laws and what we want to do are quite different things... At the same time, having many combinators that do the polyrhythmic combination thing would be very cool, I'm betting! (with the caveat that this a separate issue from the type of structure combination that happens in Applicative)

Hope that helps! Probably won't be able to respond or think much more about this until Wednesday, btw.

[yaxu]

Yes that helps thanks, and that does seem a very nice way of doing things. I'll have to try it out!

I agree that a sinewave seems both less detailed (it contains no events) and more detailed (the the higher samplerate, the more values you find).

Having more ways of combining patterns is good. I think there's a choice though between providing more operators for each, or describing how a pattern should be combined as part of its type. Neither seems completely satisfying to me..

[yaxu]

I think this should do it:

  pf <*> px = Pattern f
    where f span = catMaybes $ concat $ map match $ query pf span
            where
              match fe@((fWhole, fPart), f) = map
                                              (\((xWhole, xPart),x) -> do w <- subSpan fWhole xWhole
                                                                          p <- subSpan fPart xPart
                                                                          return ((w,p),f x)
                                              )
                                              (query px fPart)

It returns a new pattern, using the timespan you use to query it to get the events from the pattern of functions For each of these function events, it queries the pattern of values, using the part (the timespan of the event 'fragment') For each value event, it gets the intersection of it's 'whole' timespan (the span it's a fragment of), and that of the function event, and uses that as the new whole timespan. It does the same for the parts to get the new part timespan. (it does this inside the maybe monad, so it copes if the f and x events don't intersect, but they should..)

Does this make sense to anyone? :)

[bgold-cosmos]

subSpan? Is this in the refactor branch? I don't see it.

[yaxu]

Sorry I'll push everything after sleep.. subSpan is a rename of subArc

[yaxu]

Ok it's there now: https://github.com/tidalcycles/Tidal/tree/refactor/src/Sound/Tidal

I moved most of it out into a folder called 'old', am going through moving things back gradually

(I started making tests in Sound.Tidal.Test. I tried to make this into a test harness thingie integrated with cabal but gave up with some frustration. anyone familiar with this?)

[yaxu]

So far the applicative laws are testing out with this.. https://github.com/tidalcycles/Tidal/blob/refactor/src/Sound/Tidal/Test.hs#L82

[dktr0]

Cool!

[yaxu]

This approach also seems to have turned up an elegant join (aka unwrap) operation, and therefore monad: https://github.com/tidalcycles/Tidal/blob/refactor/src/Sound/Tidal/Pattern.hs#L74

[dktr0]

What is the difference between this join and the "built-in" join from Control.Monad?

[yaxu]

I think it's just that join usually has a standard definition with the meat being the definition of >>=. I'm doing it the other way around but as far as I can tell, that's an ok thing to do.

[yaxu]

Yes it seems Haskell defines a monad instance via return and bind (>>=), but that it's also possible to define one via return, join and fmap. As we already have fmap defined for the functor instance, doing this seems to make some sense..

[yaxu]

Anyway, closing this for now!