purescript / purescript-foldable-traversable Goto Github PK

like isJust <<< find, but probably this could be done better somehow if we could just loop a predicate call

I'd like to suggest adding a count function to count the number of elements that match a predicate.

Perhaps something like so:

count :: forall a f. Foldable f => (a -> Boolean) -> f a -> Int
count p = foldl (\n x -> if p x then n + 1 else n) 0

Problem

The collection packages are monomorphic for functions like (but not limited to) filter with a couple pain points:

1. They're inconvenient to use in conjunction without aliasing (e.g. List vs Array) also noted by @aspidites in tfausak/purescript-batteries#1.
2. They're inconvenient to switch out collection types to compare relative performance (thus encouraging Array use). The primary reason is type signatures must include the specialized type instead of class.

Defense

@paf31 postulated with @garyb about the potential issues of a type class solution:

1. Lack of mathematical precedence for laws.
2. Degraded performance because type class instances are currently never inlined (even when safe to do so).
3. More complex type signatures because of type class constraints. I'll add to that occasionally ambiguous inference and less friendly type errors but those are also true of this package.

Options

• Naive Cons
  • @michaelficarra implemented a naive approach for filter.
  • @AppShipIt took the same tack for partition except with singleton instead of empty to support NonEmpty types.
• Optical Cons
  • @joneshf predictably implemented Cons using Prism with examples in purescript/purescript#607.
• MonadPlus
  • @Antti demoed partition, et.al. using MonadPlus.
• (Foldable f, Unfoldable f) <= “Refoldable”
  • @jdegoes suggested Unfoldable along with @joneshf in purescript-deprecated/purescript-monoid#6 but I encountered issues attempting it.
• Witherable
  • @joneshf alternatively recommended Witherable in Haskell.
• Transducers
  • @tfausak noted (or I incorrectly inferred) Cons strikingly resembles Clojure's seq.
  • @manzyuk wrote about lawful MonoidalTransducer.
  • @Gabriel439 pointed to his Foldl.Handler in Haskell for inspiration.

Conclusion

Witherable is motivated similarly in design to Unfoldable and looks like the right fit for standard Prelude. Foldl adds the benefit of laziness and working with optics. Cons and likewise MonadPlus feel like their requirements are too specific for generic filtering but I haven't tried to think of a counterexample yet.

CC

• purescript/purescript#1075
• @bodil
• @DrBoolean
• @matthieubulte

I had an idea:

What if instead of

Map.fromFoldable $ Map.toUnfoldable someMap

You could do:

unfoldWithIndex $ foldWithIndex someMap

where

foldWithIndex   ∷ ∀ g f idx a
    . Unfoldable g
    ⇒ FolableWithIndex idx f
    ⇒ f  idx   a
    → g (idx × a)
unfoldWithIndex ∷ ∀ g f idx a
    . Foldable g
    ⇒ UnfoldableWithIndex idx f
    ⇒ g (idx × a)
    → f  idx   a

p.s. names foldWithIndex and unfoldWithIndex are arbitrary just types meter

As with moving (/=) out of Eq until we have default implementations, we could make sequence = traverse id until then also.

/cc @paf31

I have an impl of it here:

https://gist.github.com/techtangents/0a45a34782379efff983

I've defined it in terms of state, which comes from the purescript-transformers library. Unfortunately, I can't make purescript-foldable-traversable depend on purescript-transformers, as it would create a cyclic dependency. transformers has a transitive dependency on foldable-traversable.

So, I can do one of these:

• put mapAccum in a new library
• put mapAccum in transformers, instead of foldable-traversable
• rewrite mapAccum to not use state.

What would you prefer?

Essentially a shim for (flip elem). It makes sorting a little prettier:

["a", "b", "c"] # filter (flip elem ["a", "b"]) # fold
["a", "b", "c"] # filter (`elem` ["a", "b"]) # fold
["a", "b", "c"] # filter (contains ["a", "b"]) # fold

Compare to existing shims like notElem vs (\a (a # flip elem) >>> not).

Every once in a while, I find myself needing this.
Then I find this again. And then I go look it up here.

I don't know about the performance characteristics but I could translate the Haskell version into PS.

haskell: scanl (+) 0 [1,1] == [0,1,2]
purescript: scanl (+) 0 [1,1] == [1,2]

foldr, foldl and foldMap can be computed in terms of each other by use of Endo and Dual.
What do people think about providing implementations of these to be used as such:

instance foldableId :: Foldable Id where
  foldMap f (Id v) = f v
  foldr f m = foldrDefault f m
  foldl f m = foldlDefault f m

At least until we have default implementations as part of class definitions :) - or should we just wait till we can do that instead?

See default implementations of Haskell's Foldable

Seems there are specialized versions for List and Array, but no generic version - is this intentional?

The type annotation here could use a concrete type Int instead of a type variable i: https://github.com/purescript/purescript-foldable-traversable/blob/v5.0.1/src/Data/FunctorWithIndex.purs#L38

I just had to explain to a PS noob (but good at JS and UX) what intercalate does. I sent him a link to the pursuit docs quickly and then read it and realised it is basically meaningless to most people :-(

The Haskell docs are much nicer to read, I think mainly because of the example: http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html#v:intercalate

surroundMap is much easier to understand. I'll try to come up with a PR for intercalate but it was an indicator to me of just how important the docs are. This person was quite put off by them and he's been struggling partly because it feels like there isn't a nice doc resource.

Toposorted with transitive dependencies included:

• purescript-foreign
• purescript-quickcheck
• purescript-arb-instances
• purescript-maps
• purescript-sets
• purescript-const
• purescript-bifunctors
• purescript-identity
• purescript-distributive
• purescript-lens
• purescript-transformers
• purescript-lazy
• purescript-lists
• purescript-channels
• purescript-generics
• purescript-drawing
• purescript-coproducts
• purescript-inject
• purescript-tailrec
• purescript-free
• purescript-angular
• purescript-strongcheck
• purescript-argonaut
• purescript-base
• purescript-graphs
• purescript-jquery
• purescript-handlebars
• purescript-monad-eff
• purescript-mongodbf
• purescript-node-fs
• purescript-parallel
• purescript-parsing
• purescript-pattern-arrows
• purescript-sammy
• purescript-task
• purescript-streams
• purescript-string-parsers
• purescript-yargs

Foldable has no fold member and Data.Foldable defines fold = foldMap identity but Foldable1 has a fold1 member and Data.Semigroup.Foldable defines fold1Default = foldMap1 identity. Since the addition of foldr1 and foldl1 is already a breaking change, should we also remove fold1 from Foldable1 and rename fold1Default to fold1 for consistency?

There should be instances for these classes for the Lazy data type from purescript-lazy.

Do all, any, and, or terminate early (short-circuit) when encountering the first overpowering value (e.g. all can return false as soon it sees the first false).
If so, should we add a note to the docs?
If not, should we also add a note, explain why, and then point to other options to achieve this behavior?

...which is that Traversable1 is a stronger requirement, since it only requires Apply constraints on the type variable f, as opposed to Applicative. I think we should also try to come up with a convincing example of this class. What interesting Apply instances are there which are not Applicative? https://blog.functorial.com/posts/2015-12-06-Counterexamples.html lists Const k where k is a semigroup but not a monoid, and also Map k.

Perhaps the laws from GHC base could be adapted to PS?

In Haskell, scanr gives me the following:

Prelude Data.List> scanr (:) [] [1,2,3]
[[1,2,3],[2,3],[3],[]]

In Purescript, I get essentially the same output save for the missing empty list at the end.

> scanr (:) Nil [1,2,3]
[(1 : 2 : 3 : Nil),(2 : 3 : Nil),(3 : Nil)]

Is this on purpuose?

Should foldl1 and foldr1 be added either to the Foldable1 class or as helpers in the Data.Semigroup.Foldable module? They can be implemented, if awkwardly, in terms of foldMap1:

import Prelude

import Data.Monoid.Dual (Dual(..))
import Data.Newtype (alaF)
import Data.Semigroup.Foldable (class Foldable1, foldMap1)

data FoldRight1 a = FoldRight1 (a -> (a -> a -> a) -> a) a

instance foldRight1Semigroup :: Semigroup (FoldRight1 a) where
  append (FoldRight1 lf lr) (FoldRight1 rf rr) = FoldRight1 (\a f -> lf (f lr (rf a f)) f) rr

mkFoldRight1 :: forall a. a -> FoldRight1 a
mkFoldRight1 = FoldRight1 const

runFoldRight1 :: forall a. FoldRight1 a -> (a -> a -> a) -> a
runFoldRight1 (FoldRight1 f a) = f a

foldr1 :: forall a f. Foldable1 f => (a -> a -> a) -> f a -> a
foldr1 = flip (runFoldRight1 <<< foldMap1 mkFoldRight1)

foldl1 :: forall a f. Foldable1 f => (a -> a -> a) -> f a -> a
foldl1 = flip (runFoldRight1 <<< alaF Dual foldMap1 mkFoldRight1) <<< flip

but allowing instances to define their own for efficiency, as Foldable does, would be nice (in which case these could also be added as default implementations).

In Haskell's Data.Foldable, a lot of the utility functions are class members, allowing for instances to define more efficient implementations. What do people think of potentially doing this here?

It would be nice to have the asum function defined in this package.

Would be nice to have this for the various non-empty types. It would allow, for example, purescript-gen to generate arbitrary non-empty types without resorting to potentially expensive cons-style operations.

For example:

> import Data.Array
> import Data.Traversable
> import Data.Maybe
> let xs = (1..15000)
> length xs
15000

> let ys = traverse Just xs
> isJust ys

/home/harry/documents/code/purescript-sequences/.psci_modules/node_modules/Data.Maybe/index.js:0
(function (exports, require, module, __filename, __dirname) { "use strict";
^
RangeError: Maximum call stack size exceeded

There is no documentation for the module. It would be nice to give library users a sense of what this is.

Currently, Data.List.Lazy defines foldr in terms of foldl on a reversed list. This preserves stack safety.

Might it be worth sacrificing stack safety to allow foldr to work with potentially very large or infinite lists by using the naive definition (trusting the user to use a lazy operation)? If not, is that worth having as a separate function?

Sorry for the unspecific title. I'm just learning purescript. v0.1.3 must have broken something. On a fresh checkout of grunt-init-purescript I get this

>> Compiling Data.Traversable
>> Error at bower_components/purescript-foldable-traversable/src/Data/Traversable.purs line 29, column 1: 
>> Error in declaration traversableRef
>> No instance found for Prelude.Functor Data.Eq.Ref
Warning:  Use --force to continue.

Aborted due to warnings.

v0.1.2 works fine.

Has there been a reason to switch up the argument order of a and b inside the accumulator function for foldl and foldr?
I find this super confusing and have to look it up every time, I do something with Foldables.

If there isn't a reason: I would be in favor of a breaking change coming with a major version unifying these function signatures - less mental overhead. forall a b. (b -> a -> b) -> b -> f a -> b would be the more suitable one IMO, as JavaScript developers are used to Array.prototype.reduce and Array.prototype.reduceRight.

Error in declaration traversableRef
No instance found for Prelude.Functor Data.Eq.Ref

seems to be:

instance traversableRef :: Traversable Ref where
   traverse f (Ref x) = Ref <$> f x

   sequence (Ref x) = Ref <$> x

I just bumped into the problem mentioned here https://stackoverflow.com/a/38490637/3237351 and the solution was also indeed to go from foldl = foldlDefault to fold f = foldlDefault f. It feels like this could be better documented in the Foldable instance. Maybe by simply giving a trivial example like the one in SO.

Possibly adding this case to the error documentation at https://github.com/purescript/documentation/blob/master/errors/CycleInDeclaration.md would also be a good idea. I'll submit an issue there too.

Is there any reason why there is foldlM (foldM) and there is no foldrM?
I was confused because I didn't hit when I searched for this in pursuit.

foldrM :: forall a m b f. Foldable f => Monad m => (a -> b -> m b) -> b -> f a -> m b
foldrM f z0 xs = foldl c pure xs z0
  where c k x z = f x z >>= k

I find this to be a bit strange. Is there any difference that warrants one being re-exported but not the other, or was this an oversight?

Edit: this change appears to have been made in #131: https://github.com/purescript/purescript-foldable-traversable/pull/131/files#diff-4f5e121551e9770d2d2d5b35e21259033cc208f148e65fb21fc5ca87a3ecd0b3L15. product was the only function to be removed from the re-exports, so I think this was an actual oversight.

Edit 2: actually, this was removed because of an import of another, different product: https://github.com/purescript/purescript-foldable-traversable/pull/131/files#diff-4f5e121551e9770d2d2d5b35e21259033cc208f148e65fb21fc5ca87a3ecd0b3R22

Parts of the code are very clearly inspired/copied from Haskell's semigroupoids, by @ekmett. Here is its license: https://github.com/ekmett/semigroupoids/blob/master/LICENSE

It is probably worth mentioning this in the license for this repo.

If you want to get first element from some foldable you would do find (const true) but if we had index we could grab nth value from foldable and the expression above could be written like index 0 which is nicer I think. do others think that it would be a nice addition? if not why?

As far as I can tell, they're identical. At least, assuming you have a law-abiding Foldable instance (which should be a safe assumption).

If we deprecate one, I'd rather it were mconcat, but I don't feel strongly either way.

make sense?

All the indexed classes have a f -> i fundep. Isn't it conceivable, though, that a given f could have instances for different i types? With the fundep, you'd have to use Newtype to get this behavior.

See this comment in #131 for more details.

Looking at the logs it appears the access token which was being used has been revoked: https://s3.amazonaws.com/archive.travis-ci.org/jobs/239359931/log.txt?X-Amz-Expires=30&X-Amz-Date=20170612T191113Z&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Credential=AKIAJRYRXRSVGNKPKO5A/20170612/us-east-1/s3/aws4_request&X-Amz-SignedHeaders=host&X-Amz-Signature=4a657c7758063ff54363f8cc0bbef845272dba819279b6bd264d2a480dcc1da5

I have just uploaded all releases since v3.1.0 manually; I suspect other core libraries are missing docs too.

The fact that this has gone unnoticed is why I think it's better to use pulp publish locally rather than publishing as part of CI; can we reconsider this please?

Quote from the Foldable1 class documentation:

Note: some combinations of the default implementations are unsafe to use together - causing a non-terminating mutually recursive cycle. These combinations are documented per function.

However, the docs for fold1Default and foldMap1Default state nothing about this. Reading the source code of those functions, it is clear that both are unsafe to use together.

Generalize from Data.Array:

foldRecM :: forall m a b. Foldable f => MonadRec m => (a -> b -> m a) -> a -> f b -> m a

There are two ffi files here, both for array. Does it still make sense to keep them here? Or does it make more sense to move them to purescript-arrays? Near as I can tell, there's no direct dependency on arrays here, and arrays actually depends on this package instead of the other way around.

Currently, foldrDefault and foldlDefault are not stack-safe, even when given a stack-safe foldMap implementation. @natefaubion proposes a stack-safe implementation strategy for these functions here. Would you accept a pull request to make foldrDefault and foldlDefault stack-safe using this strategy? This would almost certainly make the implementation slower than the current implementation, but remain O(n).

Data.Foldable exports foldMapDefaultR and foldMapDefaultL, foldr and foldl based default implementations of foldMap, shouldn’t we also export foldMap1DefaultR and foldMap1DefaultL functions from Data.Semigroup.Foldable for consistency now that Foldable1 has foldr1 and foldl1 members?

Examples in the documentation repeatedly use a function called print. Perhaps this should be changed to log or logShow or something along those lines?

Used here.

E.g Flip currently has a Bitraversable instance but not a Traversable instance.

foldrLazy was recently added to Data.List. A somewhat controversial proposal, but maybe we should make foldr lazy by default. I liken a strict foldr in PureScript to lazy foldl in Haskell. Lazy foldl almost always uses more memory than you want, and a strict foldr almost always does more work than you want.