Stack Overflow
Stack Overflow

Questions tagged [foldable]

Foldable is a class of data structures that can be folded to a summary value.

Many of these functions generalize Prelude, Control.Monad and Data.List functions of the same names from lists to any Foldable functor. To avoid ambiguity, either import those modules hiding these names or qualify uses of these function names with an alias for this module.

class Foldable t where

Data structures that can be folded.

Minimal complete definition

[foldMap][5] | [foldr][6]

Full documentation: http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-Foldable.html

69 questions
27
votes
3 answers

Foldable, Monoid and Monad

Consider the following signature of foldMap foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m This is very similar to "bind", just with the arguments swapped: (>>=) :: Monad m => m a -> (a -> m b) -> m b It seems to me that there therefore…
Clinton
  • 22,361
  • 15
  • 67
  • 163
16
votes
2 answers

Foldr/Foldl for free when Tree is implementing Foldable foldMap?

I am a beginner at Haskell and learning from "Learn You a Haskell". There's something I don't understand about the Tree implementation of Foldable. instance F.Foldable Tree where foldMap f Empty = mempty foldMap f (Node x l r) =…
Roely de Vries
  • 213
  • 1
  • 4
13
votes
1 answer

Tree Functor and Foldable but with Nodes. Is there any generalization over it?

data Tree t = Empty | Node t (Tree t) (Tree t) We can create Functor instance and use fmap :: (t -> a) -> Tree t -> Tree a But what if instead of (t -> a) I want (Tree t -> a) so I could have access to a whole (Node t) not just t treeMap :: (Tree…
ais
  • 2,514
  • 2
  • 17
  • 24
12
votes
1 answer

Foldable vs Traversable

While studying Applicative deeper, I came to Traversable. Although I already knew Foldable from LYHGG, I haven't seen the former yet, so I started reading the Haskell wiki about Traversable. While reading it, I understood why Foldable.fold is…
FtheBuilder
  • 1,410
  • 12
  • 19
11
votes
1 answer

Why does `fmap sum Just` typecheck?

We know fmap is fmap :: Functor f => (a -> b) -> f a -> f b and sum is sum :: (Num a, Foldable t) => t a -> a, but the code below confuse me. > :t (fmap sum Just) (fmap sum Just) :: Num b => b -> b > fmap sum Just 3 3 why?
Jimmy Hu
  • 121
  • 4
10
votes
1 answer

How can I express foldr in terms of foldMap for type-aligned sequences?

I'm playing around with type-aligned sequences, and in particular I'm messing around with the idea of folding them. A foldable type-aligned sequence looks something like this: class FoldableTA fm where foldMapTA :: Category h => …
dfeuer
  • 48,079
  • 5
  • 63
  • 167
9
votes
3 answers

How does Traversable use the fact that it subclasses both Foldable and Functor?

class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) traverse g = sequenceA . fmap g sequenceA :: Applicative f => t (f a) -> f (t a) sequenceA = traverse id How does…
Tim
  • 1
  • 141
  • 372
  • 590
8
votes
1 answer

Why does mconcat require a list rather than a Foldable?

While looking at the definition of Monoid I noticed that mconcat has the following definition (source): mconcat :: Monoid a => [a] -> a mconcat = foldr mappend mempty Why would the signature limit this to [a] rather than the more generic Foldable…
fphilipe
  • 9,739
  • 1
  • 40
  • 52
8
votes
2 answers

Could it be that (Alternative f, Foldable f) => Monad f?

The following typechecks: instance (Applicative f, Alternative f, Foldable f) => Monad f where (>>=) = flip $ \f -> foldr (<|>) empty . fmap f -- Or equivalently a >>= b = getAlt . foldMap Alt . fmap b $ a Is this actually a valid Monad…
user1747134
  • 2,374
  • 1
  • 19
  • 26
7
votes
0 answers

Does a joined Bitraversable require Monad?

Despite the jargon filled title I don't think this question is very complex. Introducing the characters There are two important Functor combinators at play here. Flip equivalent to the haskell functiong flip but operating on types newtype Flip p a…
Wheat Wizard
  • 3,982
  • 14
  • 34
7
votes
2 answers

Why in Haskell maximum (8,1) = 1?

I have just started learning Haskell. As I know maximum gives the max value for a list of integers. So, maximum [2,5,7,1] gives 7. But why by giving a tuple input does maximum always give the second element? E.g., maximum (8,1) gives 1. The same…
Supriyo Halder
  • 200
  • 1
  • 7
7
votes
3 answers

Why isn't sum == foldl1 (+)?

I sum a list of matrices with foldl1 (+) because I noticed that sum actually returns the sum of the top left elements as a 1x1 matrix. $ stack exec --resolver lts-12.5 --package matrix -- ghci GHCi, version 8.4.3: http://www.haskell.org/ghc/ :?…
peer
  • 4,171
  • 8
  • 42
  • 73
7
votes
2 answers

Can I write `foldr` (or `foldMap`) in terms of 'recursion schemes' `cata`?

I recently read about recursion schemes where catamorphisms are described as analogous to generalized foldr. Is is possible to write an instance of Foldable (via either foldr or foldMap) in terms of cata in all cases?
Michael Thomas
  • 1,354
  • 7
  • 18
7
votes
2 answers

What does Traversable is to Applicative contexts mean?

I am trying to understand Traversable with the help of https://namc.in/2018-02-05-foldables-traversals. Somewhere the author mentioned the following sentence: Traversable is to Applicative contexts what Foldable is to Monoid values. What did…
softshipper
  • 32,463
  • 51
  • 192
  • 400
7
votes
2 answers

Is there anything we lose with MonoFoldable?

MonoFoldable in the mono-traversable package seems to be able to implement all of the usual Foldable containers and more, for example, things like Bytestring and homogeneous tuples can be made MonoFoldable but not Foldable. My question is, do we…
Clinton
  • 22,361
  • 15
  • 67
  • 163
1
2 3 4 5