Add API: sliding and slidingSizeStep

[JordanMartinez]

Backlinking to #212 for more context. The question here is whether to add sliding, a function that returns windows of the array, and what its type signature should be. A variation of sliding is slidingSizeStep which allows one to control the size of the window and how far to step before creating a new window. We'll cover this function later in this issue.

Starting with sliding, the core question is what the return type should be. Below, I'll refer to various ideas for implementations using _N where N refers to the possible way forward.

-- as proposed in #212
_1 :: forall a. Array a -> Array (Tuple a a)

_2 :: forall a. Array a -> Array { previous :: Maybe a, current :: a, next :: Maybe a }

_3 :: forall a b. Array a -> (Tuple a a -> b) -> Array b 

_1 is what is proposed in #212. _2 is what Harry proposed in his comment, functioning more like a Zipper. _3 is something I am proposing for unifying the other two. For example, if we implemented _1 and _3 in this library, _2 could still easily be implemented via (Tuple l r) -> {previous: Nothing, current: l, next: Just r}.

Since _2's zipper-like type might want additional features (e.g. a Functor instance) that is largely outside the scope of this project, I propose not implementing it as end-users can implement it and define their own Window type. Moreover, _3 enables more potential use cases we cannot imagine right now (e.g. slidingF ((Tuple l r) -> l + r) [0, 1, 2, 3] would produce [1, 3, 5]), simulating a scanl like feature.

---

Let's move on to slidingSizeStep. If we ignore the size and step arguments in the function, the question arises again as to what the return type should be. Here's two factors that come to mind:

1. whether the returned value is Array _ or Maybe (NonEmptyArray _)
2. whether the returned value is the complete subcollection or a zipper-like value

-- as proposed in #212
_11 :: forall a. Array a -> Array (NonEmptyArray a)

_12 :: forall a. Array a -> Maybe (NonEmptyArray (NonEmptyArray a))

_13 :: forall a. Array a -> Array { before :: List a, current :: a, after :: List a }

_14 :: forall a b. Array a -> (NonEmptyArray a -> b) -> Array b 

I believe _11 is to be preferred over _12 because one can still get Foldable1 and friends without having to pay for the Just constructor unwrapping in _12 by doing something like this:

case NEA.fromArray $ slidingSizeStep [0, 1, 2, 3] of
  Nothing -> -- returned array is empty
  Just nea -> fold1 nea -- returned array is non-empty

_13 provides the same zipper-like idea. However, it cannot be implemented because arrays does not depend on lists. Working similar to sliding, _4 provides an escape hatch to this problem. One could use _4 in combination with my own arrays-zipper to get an Array-based zipper or use pointed-list to get a List-based zipper.

---

In conclusion, I propose we implement these four functions:

sliding :: forall a. Array a -> Array (Tuple a a)
sliding = slidingF identity

slidingF :: forall a b. (Tuple a a -> b) -> Array a -> Array b
slidingF = ...

slidingSizeStep :: forall a. Int -> Int -> Array a -> Array (NonEmptyArray a)
slidingSizeStep size step = slidingSizeStepF size step identity

slidingSizeStepF :: forall a b. Int -> Int -> (NonEmptyArray a -> b) -> Array a -> Array b 
slidingSizeStepF size step f arr = ...

I'm not yet considering rangeWithStep that was also proposed in #212 because I want to first cover these two functions and their variations.

[JordanMartinez]

While the comment I made above discusses the design of the API, it does not ask whether the functionality should be added here. Does such sliding functionality appear in other language's standard libraries? If it does, I think that's a strong argument for supporting it here.

[FloWi]

Thanks for the writeup, @JordanMartinez. I come from scala and it has a very powerful collection library that's part of the standard-library. I missed this function for my side-project so I decided to write it in purescript ;-) see here.
It returns an Iterator[List[A]] which is a lazy datastructure. Oh, and they don't have the version with the tuple.

[JordanMartinez]

Ah... I forgot about the possibility of returning a lazy data structure. I'm wondering what the pros/cons of that would be.

Personally, I'm not sure I'd want the Tuple version either.

It also looks like the Iterator type is a mutable data structure that follows most OO patterns of that idea. A Zipper would be a corresponding counterpart for FP.

[JordanMartinez]

I think it would be easier to implement functions like sliding and slidingSizeStep outside of this repo if #182 were implemented.