purescript / purescript-arrays Goto Github PK

Given the type of runSTArray:

runSTArray ::
  forall a r.
    (forall h. Eff (st :: ST h | r) (STArray h a)) -> Eff r (Array a)

it seems to me that it's a nice alternative to freeze + runST, which would involve an unnecessary copy, but I can't see a way to take advantage of this if I want to return more than one STArray from the computation. This would be helpful, for example, for efficiently implementing functions like unzip. Can anyone think of a good way of addressing this?

Just like the methods of the same names on a JS Array:

• pop removes the last item of an array and returns that item
• shift removes the first item of an array and returns that item
• unshift takes an item and sets it as the first element of the array, shifting everything else along by 1

This would be useful for the Data.List library I'm working on, to implement toList efficiently.

I'm just keeping this here as a note for myself.

This is perfectly safe, due to state thread scopes, yet currently the docs suggest that people use unsafeFreeze manually.

Data.Array.ST exports unsafeFreeze and unsafeThaw but the foreign object version of unsafeFreeze is exported from Foreign.Object.ST.Unsafe and in purescript/purescript-record#68 I proposed to export record versions of these from Record.ST.Unsafe. Should we extract them to a new Data.Array.ST.Unsafe module for consistency?

Very useful functions for combining arrays of monoids (like strings)

A common use case is to just keep the original array instead of returning Nothing when the index is out-of-bounds, like so:

updateAt_ :: forall a. Int -> a -> Array a -> Array a
updateAt_ i x xs = fromMaybe xs (updateAt i x xs)

Should these wrappers be included in this library? Thoughts on naming?

There's an opportunity to add another version of updateAtIndices that returns Nothing when any index is out of bounds. Would this be useful? Might need to rename the original for consistency:

-- original (name changed)
updateAtIndices_ :: forall t a. Foldable t => t (Tuple Int a) -> Array a -> Array a
-- new (name overwrite)
updateAtIndices :: forall t a. Foldable t => t (Tuple Int a) -> Array a -> Maybe (Array a)

Data.List.Lazy's updateAt has similar behavior to the existing updateAtIndices, and returns the original List when out-of-bounds. I assume there can't be another version with Maybe, since that would defeat the benefits of laziness.

-- original
updateAt :: forall a. Int -> a -> List a -> List a
-- considered
maybeUpdateAt :: forall a. Int -> a -> List a -> Maybe (List a)

The result structure for partition is a bit idiosyncratic:

partition :: forall a. (a -> Boolean) -> Array a -> { yes :: Array a, no :: Array a }

I get the impression that, over time, purescript APIs have been preferring Tuples for this kind of thing, rather than ad-hoc records. What do people think of either (breaking) switching the API to returning a Tuple, or making a partition' that returns Tuples?

For comparison, partition from the Haskell prelude:

partition :: (a -> Bool) -> [a] -> ([a], [a])

Looks like head isn't O(1), at least on node v4.4.7.

I measured with purescript-benchotron as follows:

benchHead :: Benchmark
benchHead = mkBenchmark
  { slug: "head"
  , title: "Head of a structure"
  , sizes: (1 .. 8) <#> (_ * 150)
  , sizeInterpretation: "Number of elements in the structure"
  , inputsPerSize: 1
  , gen: randomArray
  , functions: [ benchFn "Array" A.head
               , benchFn "Array'" (_ `A.index` 0)
               ]
  }

I think it should be the same as delete and return Array instead of Maybe.
If I care about existence of the index I can use length for checking.

Because Array.slice has complexity 0(n), many of the functions in Data.Array have a worse complexity than they should have.
head is O(n) instead of O(1)
last is O(n^2) where it could be O(1)
tail is O(n) (due to copying instead of sharing)

I find that pattern matching on Arrays using cons syntax is generally a bad idea. It almost always leads to worse performance than expected. Functional programmers are used to pattern matching being free (O(1)). By having
cons patterns which are O(n), it may confuse programmers and give unexpected performance penalties.
The examples shown on the patterns documentation (sum and addPairs) are also O(n^2).

Libraries that wish to build upon this one have to implement their own FFI when trying to maximize performance. So, could we expose the FFI here, so that it's more backend-friendly?

At the moment, arrays imports modules from maybe, and exports functions which contain Maybe types, but maybe isn't specified in the bower.json file. Perhaps it would be worth adding it, rather than relying on it being pulled in transitively?

Perhaps it would be useful, if we get a package manager specifically for purescript, for it to enforce this automatically.

fromFoldableImpl currently uses foldr. Shouldn't it be possible to write a foldl-based implementation? Generally speaking, the foldl implementations for core PS data structures seem to be more efficient, if only because they can avoid tricks needed for stack safety.

Replicate has been removed. But it was useful and efficient. Can you show me an alternative way with equal or better performance? Otherwise please undo this change

i see sortBy/sortWith, but only groupBy.
Minor convenience but it would be nicely parallel, and this missing one is often what I want: Theres no new logic, I just need to dive into some structure.

In accordance to group' it should first sort the Array and then group it.

Btw: Why not name it sortAndGroup or sortGroup or groupSort or anything more intuitive then group'? ^^

Would be nice to see an adaptation of Haskell's accumArray, which gives a handy shortcut around using ST to build an array.

No doubt it's intentional. Same stuff for purescript-lists.
My guess is that map is not exposed to not collide with Prelude.map. This has downsides, though.

1. Educational. I can't say "import Data.Array as Array and use concrete types before you're ready to functors", because the most important function isn't there.

2. Namespacing. Special rule for map in Array.concatMap _ >>> map _ >>> Array.whatever _ kind of constructions is annoying. You can say it's a matter of habit, but in JS I use qualified imports almost exclusively. So I expected to do the same in PureScript. Maybe it's not a pragmatic approach (because operators) – you tell me.

Btw. can we namespace operators like Array.(..) or something?

3. Consistency. The presence of generic map makes Array.map unnecessary? Well, there's Control.Bind.bindFlipped and there's Array.concatMap so no. I'm sure there are more functions in Array that have generic counterparts.

map is an exception and PureScripts is a language that doesn't favor exceptions. So a question.

pushSTArray, pokeSTArray, etc. could be exported as push and poke. Library users could use qualified imports for disambiguation.

Let me start by saying that I really like how head, tail and other functions in this module are safe by default (compared to Haskell). Considering this, it seems strange to me that findIndex (and three related functions) have the type

findIndex :: forall a. (a -> Boolean) -> [a] -> Number

and fail with -1. While this is technically not 'unsafe' behavior, the -1 should not be used as an array index. Right now, I don't see how the -1 value is useful other than signalling failure. For me, it would feel more natural if the type would simply be

findIndex :: forall a. (a -> Boolean) -> [a] -> Maybe Number

and failure would be indicated by Nothing.

This seems weird:

union [0, 0] [1, 1] == [0, 0, 1]

I would have expected the result to be [0, 1], but at least it should be symmetrical in both arguments. I would consider several possible fixes:

1. Remove all duplicates (i.e. union a b == nub (a <> b))
2. Keep the duplicates within both of the arguments (i.e. union [0, 0] [1, 1] == [0, 0, 1, 1]).
3. Remove union and unionBy from Data.Array (given that Set is the better data structure for something like this)
4. Document the behavior if it is intended

I would vote for 1 or 3.

Currently we use an Eq constraint for functions like nub and difference. However this gives a poor asymptotic complexity; see https://github.com/nh2/haskell-ordnub.

Of course, there are some types which have Eq but not Ord instances so it makes sense to make Eq versions of these functions available. However, most types do have Ord instances so I think the default version should use Ord. That is, I'd prefer to have nub :: forall a. Ord a => Array a -> Array a and additionally nubEq which is the same except with only an Eq constraint.

This is a little bit difficult with respect to dependencies because we would probably want to depend on sets to do this, but maps (which is a dependency of sets) already depends on arrays. So that's one issue to sort out, if we do agree that we want to do this.

The compilation of (!!) function fails by the lack of complement function used in isInt function (l.78).

Rather, I prefer to define isInt as follows by calling inline JavaScript function.

isInt n = foreign import isInt
 "function isInt(n) { return ( Math.floor(n) === n ); }" :: Number -> Boolean 

In following example:

arr :: Array Int
arr = [1,2,3,4,5]

test :: String
test = show $ A.groupBy (\_ _ -> true) arr

Expected value of the function test:

[(NonEmptyArray [1,2,3,4,5])]

Actually:

[(NonEmptyArray [2,3,4,5,1])]

The first element is placed at the end of array.

e.g. head xs <|> x

While most of the time we use NonEmptyList, there are some times we need either a NonEmpty Array or would have a use for NonEmptyArray.

Probably there would not be much more than a copy of NonEmptyList for arrays and then a few convenience functions like Array a -> Maybe (NonEmptyArray a)?

The following line:

causes runtime errors when compiled with purs bundle, because replicatePolyfill gets eliminated as dead code.

I'm not sure if it is a purs bundle bug, since I don't understand exactly the spec of the code elimination it performs (in particular, what shapes of exports it supports).

On my machine I am getting a RangeError when using concat on an array with 150,000 elements; e.g.,

function concat (xss) {
  var result = [];
  for (var i = 0, l = xss.length; i < l; i++) {
    result.push.apply(result, xss[i]);
  }
  return result;
}

var as = new Array(150000);
var bs = concat([as]);

$ node index.js

/index.js:4
    result.push.apply(result, xss[i]);
                ^
RangeError: Maximum call stack size exceeded

All undefined elements are sorted to the end of the array, with no call to compareFunction.

— https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#Description

Therefore, sorting on any type inhabited by undefined will not use the correct ordering (except by coincidence). This is also a parametricity violation.

The only truthful use of native sort is on JavaScript values.

I propose we replace the implementation with a correct one. Yes, it will be slower. We might define unsafeSort to use the native sort with the same typing as sort. Then we may also have a different sort definition typed on JavaScript values (which is Foreign).

I would like to be able to create an array using one of the existing functions for immutable arrays (e.g. range), and then use it locally within a function, but not return a reference to it. I would also like to be able to do this with a minimum of copying. Currently I think the best I can do is to use thaw or withArray, which make a copy of it; if I know that no references to my array can escape I should be able to get away without copying it. Could we possibly add an unsafeThaw, which has the same type as thaw but just returns a reference to the same array instead of copying?

x :: Array Int
x = []
y = 1 + Data.Array.Unsafe.head x

Doesn't have any errors and

y == 0

I don't think this is a correct behavior

I think the exported index function has terrible performance for such a low level operation, and adds unnecessary code complexity where it is used. I suggest renaming indexImpl to indexMaybe and exporting it. This way, one could define, for example:

indexInt :: Array Int -> Int -> Int
indexInt = indexMaybe id 0

And similar, which are much more convenient, readable and faster versions of index.

I will submit a PR if agreed.

E.g. this implementation does not crash and is more efficient, but it has an additional type class constraint. I'm not aware of the implications of this constraint

foldM :: forall m a b. MonadRec m => (a -> b -> m a) -> a -> Array b -> m a
foldM func init array = tailRecM2 go init 0
  where
    go res index | index >= length array = pure (Right res)
    go res index                         = do
        res' <- func res (unsafePartial (unsafeIndex array index))
        pure $ Left {a:res', b:(index + 1)}

Typeclass instances for STArray?

Using peekSTArray and pokeSTArray from Data.Array.ST.Partial yields a runtime error:
TypeError: Cannot read property '[object Array]' of undefined
The generated JavaScript for peekSTArray looks like this:

exports.peekSTArray = function (xs) {
  return function (i) {
    return function () {
      return xs[i];
    };
  };
};

But is called like this:
Data_Array_ST_Partial.peekSTArray(dictPartial)(a)(i)();
I.e. xs[i] ends up as dictPartial[a].
I suspect this is because of peekSTArray being imported like:

foreign import peekSTArray
  :: forall a h r
   . Partial
  => STArray h a
  -> Int
  -> Eff (st :: ST h | r) a

instead of

peekSTArray
  :: forall a h r
   . Partial
  => STArray h a
  -> Int
  -> Eff (st :: ST h | r) a
peekSTArray = peekSTArrayImpl

foreign import peekSTArrayImpl
  :: forall a h r
   . STArray h a
  -> Int
  -> Eff (st :: ST h | r) a

which is used instead in some places, for instance unsafeIndex from Data.Array.
The same is true for pokeSTArray.

I apologize if this is not actually an issue; I am very new to the FP world and only started learning PureScript a few days ago.

I'm thinking this will be better because it won't continue to process the remainder of the array after finding a match.

find :: forall a. (a -> Boolean) -> Array a -> Maybe a
find p xs = findIndex p xs >>= index x

The implementation of many array functions, like filterM, span, groupBy, ... uses uncons for implementation. It would be more efficient to use an index and has no known disadvantages (other then maybe some subjective aesthetic property).

If we can agree on this I can contribute code, but I don't want to work on this if it is not wanted.

Now that there's a NonEmptyArray, these functions should be updated.

What you think to add similar functions?
do you like this names?
https://lodash.com/docs/4.17.4#dropRight
https://lodash.com/docs/4.17.4#takeRight

dropRight n arr = take (length arr - n) arr
takeRight n arr = drop (length arr - n) arr

cf. purescript-lists/#53

I need slice for matrices (purescript-matrix package). I would like to see this exported, as I don't need to replicate the function then.
I think it is justified in the interface, as arrays are arrays and not lists.

Shouldn't fromFoldable1 have partial in its type?

fromFoldable1 :: forall f a. Partial => Foldable1 f => f a -> NonEmptyArray a

Haskell:

Prelude> take (-1) [1,2,3]
[]
Prelude> drop (-1) [1,2,3]
[1,2,3]

PureScript:

> take (-1) [1,2,3]
  [1,2]

> drop (-1) [1,2,3]
  [3]

I haven't seen the differences documented anywhere. If these are intended, a note in https://github.com/purescript/purescript/wiki/Differences-from-Haskell would be nice.

IMHO take/drop should keep haskell semantics and 'slice' should be exported keeping JS semantics.

To complement the ST interface, like we have for records.