import { Functor } from "./functor" ; import { Foldable , AbstractFoldable } from "./foldable" ; import { Applicative , AbstractApplicative , ApplicativeDictionary } from "./applicative" ; import Identity from "./identity" ; import Endo from "./monoids/endo" ; import { ConstEndo } from "./const" ; import { id , mixin , cons } from "./utils" ; export interface Traversable < A > extends Functor < A > , Foldable < A > { traverse < B > ( a , f ) : Applicative < Traversable < B > > ; sequence < B > ( a , t ) : Applicative < Traversable < B > > ; } export abstract class AbstractTraversable < A > extends AbstractFoldable < A > implements Traversable < A > { map < B > ( f ) { return ( < any > this . traverse ( Identity , ( a ) => Identity . of ( f ( a ) ) ) ) . extract ( ) ; } mapTo < B > ( b ) { return this . map ( ( _ ) => b ) ; } traverse < B > ( a , f ) { return this . sequence ( a , this . map ( f ) ) ; } sequence < A > ( a , t ) { return t . traverse ( a , id ) ; } foldr < B > ( f , acc ) { const f2 = ( a ) => new ConstEndo < B , B > ( new Endo ( ( b ) => f ( a , b ) ) ) ; return Endo . toFunction ( ( < ConstEndo < B , B > > ( < any > this . traverse ( ConstEndo , f2 ) ) ) . get ( ) ) ( acc ) ; } } export function traversable ( constructor ) { const p = constructor . prototype ; if ( ! ( "map" in p && "sequence" in p ) && ! ( "traverse" in p ) ) { throw new TypeError ( "Can't derive traversable. Either `traverse` or `map` and `sequence` must be defined." ) ; } mixin ( constructor , [ AbstractTraversable , AbstractFoldable ] ) ; } function arraySequence < A > ( a , t ) { let result = a . of < A [ ] > ( [ ] ) ; const lift = result . lift ; for ( let i = t . length - 1 ; i >= 0 ; -- i ) { result = lift < A , A [ ] , A [ ] > ( cons , t [ i ] , result ) ; } return result ; } function arrayTraverse < A , B > ( a , f , t ) { let result = a . of < B [ ] > ( [ ] ) ; const lift = result . lift ; for ( let i = t . length - 1 ; i >= 0 ; -- i ) { result = lift < B , B [ ] , B [ ] > ( cons , f ( t [ i ] ) , result ) ; } return result ; } export function sequence < A > ( a , t ) ; export function sequence < A > ( a , t ) ; export function sequence < A > ( a , t ) { if ( t instanceof Array ) { return arraySequence ( a , t ) ; } else { return t . sequence ( a , t ) ; } } export function traverse < A , B > ( a , f , t ) ; export function traverse < A , B > ( a , f , t ) ; export function traverse < A , B > ( a , f , t ) { if ( t instanceof Array ) { return arrayTraverse ( a , f , t ) ; } else { return t . traverse ( a , f ) ; } } class AnApplicative < A , B > extends AbstractApplicative < B > { constructor ( private f ) { super ( ) ; } of < B > ( b ) { return new AnApplicative ( ( a ) => [ a , b ] ) ; } static of < B > ( b ) { return new AnApplicative ( ( a ) => [ a , b ] ) ; } ap < C > ( fa ) { return new AnApplicative ( ( a ) => { const [ a1 , b ] = this . f ( a ) ; const [ a2 , f ] = fa . f ( a1 ) ; return [ a2 , f ( b ) ] ; } ) ; } run ( a ) { return this . f ( a ) ; } } export function mapAccumR < A , B , C > ( f , init , t ) { return ( < any > t . traverse ( AnApplicative , ( a ) => new AnApplicative ( ( c ) => f ( c , a ) ) ) ) . run ( init ) ; }