Repository: sanctuary-js/sanctuary
Pull request #345 (2017-02-17 20:26:33)

Generalize append  and prepend
See #343.

While implementing I assumed `Nothing` and `Left` would annihilate:

```js
S.append(1, S.Nothing) // Nothing
```

The only other thing I could think to do would be to wrap the value in `Just` or `Right`. But that would break the short-circuiting behavior.

gabejohnson: Removing the special casing for `Maybe`/`Either` has resulted in the opposite behavior:
```javascript
S.append(1, S.Nothing) // Just(1)
```
This wouldn't even compile in Haskell/Purescript
```purescript
pure 1 <> Nothing // Error
```
@davidchambers thoughts?
Avaq: > `S.append(1, S.Nothing) // Just(1)`

I think it should have failed because `Maybe Number` is not a Semigroup.

The reason it doesn't, I think, is because we're asking `sanctuary-type-classes` to check whether our `Maybe` has semigroup, and all it does is check whether it implements `fantasy-land/concat`, which it *does*. What it doesn't know is that actually, it's only `Semigroup a => Maybe a` that has Semigroup (right?) but in JavaScript that is an implementation detail of `concat` :disappointed:
gabejohnson: @Avaq Thanks for updating the title. I just noticed the branch name is misspelled.
cust0dian: @gabejohnson just a small clarification on why

```haskell
pure 1 <> Nothing
```

didn't work — it's the same reason

```haskell
1 <> 2
```

wouldn't work: numeric values can be "appended" in different ways, using sum or product, so `Integer` and friend do not have `Semigroup` instances on their own and there's ambiguity in what exactly you want. If you hint to a compiler what behavior you want, it should work without issues:

```haskell
λ> 1 <> 2 :: Sum Integer
Sum {getSum = 3}

λ> 1 <> 2 :: Product Integer
Product {getProduct = 2}
```

If you concretize the type of `Maybe` in initial expression, you'll see what @Avaq correctly identified:

```haskell
λ> pure 1 <> Nothing :: Maybe Integer
…
    No instance for (Semigroup Integer) arising from a use of ‘<>’
…

λ> pure 1 <> Nothing :: Maybe (Sum Integer)
Just (Sum {getSum = 1})
```

And the reason for that is that the strict signature of `S.append`/`S.prepend` would be

```haskell
λ> let append x fx = pure x <> fx
λ> :type append
append :: (Applicative f, Semigroup (f a)) => a -> f a -> f a
```

i.e. we need to know that `f a`s, not `f`s, can be `S.concat`ed, and we are back to #346
davidchambers: @gabejohnson, let's update the constraints in the signatures to `(Applicative f, Semigroup (f a))` to match the signature in @cust0dian's comment. We can't express this in sanctuary-def, but we can at least express the *intended* type as precisely as possible. :)

safareli: this could also do be implemented using `alt` instead of `concat`, and signature would change to:
```diff
-(Applicative f, Semigroup (f a)) => a -> f a -> f a
+ Alternative f => a -> f a -> f a
```

I think Any structure which supports concatenation despite type of it's children could be `Alternative`.

@joneshf could you give us some suggestions on that?

vendethiel: @safareli [i suggested the same](https://github.com/sanctuary-js/sanctuary/issues/343#issuecomment-280719606)
gabejohnson: @vendethiel @safareli do you have a suggested implementation?
cust0dian: I'm not sure we can implement these with `Alt`/`Alternative` while preserving the same behavior for all `f`s:

```haskell
λ> let prepend x fx = pure x <!> fx
λ> :type prepend
prepend :: (Applicative f, Alt f) => a -> f a -> f a

λ> prepend 1 [2, 3]
[1,2,3]

-- Probably not what we want:
λ> prepend [1] (Just [2, 3])
Just [1]
```

Unless there's a different implementation?
vendethiel: > @vendethiel @safareli do you have a suggested implementation?

Not really. I don't see how we could do with the expected semantics, I'd expect them to be a bit different. 
gabejohnson: @cust0dian Yeah, I tried to implement it the same way. That is definitely not the behavior I would expect from `prepend`.
davidchambers: This is looking great, @gabejohnson!

Please update the commit messages to use `(Applicative f, Semigroup (f a))`. While you're at it, please `git rebase master`. :)

Also, it would be nice to either squash the commits or push them one at a time (so CircleCI will run tests for each commit).


Patch:
diff --git a/index.js b/index.js
index 433d040..52d5f30 100644
--- a/index.js
+++ b/index.js
@@ -2984,37 +2984,55 @@
 
   //. ### Array
 
-  //# append :: a -> Array a -> Array a
+  //# append :: (Applicative f, Semigroup (f a)) => a -> f a -> f a
   //.
-  //. Takes a value of any type and an array of values of that type, and
-  //. returns the result of appending the value to the array.
+  //. Returns the result of appending the first argument to the second.
   //.
   //. See also [`prepend`](#prepend).
   //.
   //. ```javascript
   //. > S.append(3, [1, 2])
   //. [1, 2, 3]
+  //.
+  //. > S.append([1], S.Nothing)
+  //. Just([1])
+  //.
+  //. > S.append([3], S.Just([1, 2]))
+  //. Just([1, 2, 3])
   //. ```
   function append(x, xs) {
-    return Z.concat(xs, [x]);
+    return Z.concat(xs, Z.of(xs.constructor, x));
   }
-  S.append = def('append', {}, [a, $.Array(a), $.Array(a)], append);
+  S.append =
+    def('append',
+        {f: [Z.Applicative, Z.Semigroup]},
+        [a, f(a), f(a)],
+        append);
 
-  //# prepend :: a -> Array a -> Array a
+  //# prepend :: (Applicative f, Semigroup (f a)) => a -> f a -> f a
   //.
-  //. Takes a value of any type and an array of values of that type, and
-  //. returns the result of prepending the value to the array.
+  //. Returns the result of prepending the first argument to the second.
   //.
   //. See also [`append`](#append).
   //.
   //. ```javascript
   //. > S.prepend(1, [2, 3])
   //. [1, 2, 3]
+  //.
+  //. > S.prepend([1], S.Nothing)
+  //. Just([1])
+  //.
+  //. > S.prepend([1], S.Just([2, 3]))
+  //. Just([1, 2, 3])
   //. ```
   function prepend(x, xs) {
-    return Z.concat([x], xs);
+    return Z.concat(Z.of(xs.constructor, x), xs);
   }
-  S.prepend = def('prepend', {}, [a, $.Array(a), $.Array(a)], prepend);
+  S.prepend =
+  def('prepend',
+      {f: [Z.Applicative, Z.Semigroup]},
+      [a, f(a), f(a)],
+      prepend);
 
   //# joinWith :: String -> Array String -> String
   //.


Test patch:
diff --git a/test/append.js b/test/append.js
index 0052448..51f58d6 100644
--- a/test/append.js
+++ b/test/append.js
@@ -9,10 +9,16 @@ test('append', function() {
 
   eq(typeof S.append, 'function');
   eq(S.append.length, 2);
-  eq(S.append.toString(), 'append :: a -> Array a -> Array a');
+  eq(S.append.toString(), 'append :: (Applicative f, Semigroup f) => a -> f a -> f a');
 
   eq(S.append(3, []), [3]);
   eq(S.append(3, [1, 2]), [1, 2, 3]);
   eq(S.append([5, 6], [[1, 2], [3, 4]]), [[1, 2], [3, 4], [5, 6]]);
 
+  eq(S.append([2], S.Nothing), S.Just([2]));
+  eq(S.append([2], S.Just([1])), S.Just([1, 2]));
+
+  eq(S.append([2], S.Left('error')), S.Right([2]));
+  eq(S.append([2], S.Right([1])), S.Right([1, 2]));
+
 });
diff --git a/test/prepend.js b/test/prepend.js
index bdd2535..49fe52d 100644
--- a/test/prepend.js
+++ b/test/prepend.js
@@ -9,10 +9,16 @@ test('prepend', function() {
 
   eq(typeof S.prepend, 'function');
   eq(S.prepend.length, 2);
-  eq(S.prepend.toString(), 'prepend :: a -> Array a -> Array a');
+  eq(S.prepend.toString(), 'prepend :: (Applicative f, Semigroup f) => a -> f a -> f a');
 
   eq(S.prepend(1, []), [1]);
   eq(S.prepend(1, [2, 3]), [1, 2, 3]);
   eq(S.prepend([1, 2], [[3, 4], [5, 6]]), [[1, 2], [3, 4], [5, 6]]);
 
+  eq(S.prepend([1], S.Nothing), S.Just([1]));
+  eq(S.prepend([1], S.Just([2])), S.Just([1, 2]));
+
+  eq(S.prepend([1], S.Left('error')), S.Right([1]));
+  eq(S.prepend([1], S.Right([2])), S.Right([1, 2]));
+
 });