Bifoldable

Intuitively a bifoldable is a type with 2 arguments, each of them being foldable.

A bifoldable (short for binary foldable) or foldable of two variables is a container of up to two elements whose components can be folded to a single value.

Unlike bimap which preserves the container type, bifoldable will extract and fold the value.

Minimal complete definition

• bifoldMap f g x

static member BifoldMap (x:'Bifoldable<'T,'V>, f:'T->'U, g:'V->'U) :'U

• bifold f g z x

static member Bifold (x:'Bifoldable<'T,'V>, f:'T->'Monoid, g:'V->'Monoid, z: 'Monoid) :'Monoid

• bifoldBack f g x z

static member BifoldBack (x:'Bifoldable<'T,'V>, f:'T->'Monoid, g:'V->'Monoid, z: 'Monoid) :'Monoid

Other operations

• bisum x

static member Bisum (x:Bifunctor<'T,'T>) :'T

Rules

bisum x = bifoldMap id id x
bifoldMap f g x = bifoldBack (f >> (++)) (g >> (++)) x zero
bifoldBack f g x z = Endo.run (bifoldMap (f >> Endo) (g >> Endo) x) z

Related Abstractions

• Foldable: All bifoldable contain up to two elements that are foldable to a single common type.
• Monoid: For containers where the two elements are not disjoint, the same relation that foldable has to monoid applies.

Concrete implementations

From .Net/F#

• 'T * 'U
• struct ('T * 'U)
• Result<'T, 'U>
• Choice<'T, 'U>

From F#+

• Const<'C, 'T>
• Validation<'Error, 'T> Suggest another concrete implementation

Examples

#r @"../../src/FSharpPlus/bin/Release/netstandard2.0/FSharpPlus.dll"

open FSharpPlus
open FSharpPlus.Control

let listMapSeqLength = List.map Seq.length
let listMapTimes2 = List.map ((*) 2)

let c1 : Choice<int list,string list> = Choice1Of2 [1..2]
let c2 : Choice<int list,string list> = Choice2Of2 ["a";"bbbb"]

bifoldBack (listMapSeqLength >> (++)) (listMapTimes2 >> (++)) c1 [0] // = [2;4;0]
bifoldBack (listMapSeqLength >> (++)) (listMapTimes2 >> (++)) c2 [0] // = [1;4;0]
bifoldMap listMapSeqLength listMapTimes2 c1 // = [2;4]
bifoldMap listMapSeqLength listMapTimes2 c2 // = [1;4]

let t = ("b","c")
bifoldBack (++) (++) t "a" // = "bca"
bifold (++) (++) "a" t // = "abc"

// implementing on custom type:
type MyEither<'a,'b> = 
    | MyLeft of 'a 
    | MyRight of 'b
    static member inline BifoldMap (x: MyEither<_,_>, f, g) =
      match x with
      | MyLeft a -> f a
      | MyRight a -> g a

    static member BifoldBack (x: MyEither<_,_>, f, g, z) =
        match x with
        | MyLeft a -> f a z
        | MyRight a -> g a z

bisum (MyEither.MyLeft "a") // = "a"
bisum (1,2) // = 3


let inline law1 x =
  bisum x = bifoldMap id id x

law1 (1,1) // = true
law1 (Ok [1;2;3]) // = true
law1 (Error [1;2;3]) // = true
law1 (Choice1Of2 [1;2;3]) // = true
law1 (Choice2Of2 [1;2;3]) // = true
law1 (MyLeft [1;2;3]) // = true
law1 (MyRight [1;2;3]) // = true


let inline law2 x f g =
  bifoldMap f g x = bifoldBack (f >> (++)) (g >> (++)) x zero

law2 (1,1) ((+) 1) ((+) 2) // = true
law2 (Ok [1;2;3]) ((++) [1]) ((++) [2]) // = true
law2 ("a","b") ((+) "bbbb") ((+) "aaaa") // = true

open FSharpPlus.Data
let inline law3 x f g z =
  bifoldBack f g x z = Endo.run (bifoldMap (f >> Endo) (g >> Endo) x) z

law3 (1,1) (++) (++) 5 // = true
law3 ("a","b") (++) (++) "abcd" // = true
law3 (Ok [1;2;3]) (++) (++) [0;1;2;3;4] // = true