since import { Applicative as ApplicativeHKT , Applicative1 } from 'fp-ts/lib/Applicative' ; import { Apply1 } from 'fp-ts/lib/Apply' ; import * as A from 'fp-ts/lib/Array' ; import * as Eq from 'fp-ts/lib/Eq' ; import { Foldable1 , intercalate } from 'fp-ts/lib/Foldable' ; import { flow , Predicate , Refinement } from 'fp-ts/lib/function' ; import { Functor1 } from 'fp-ts/lib/Functor' ; import { HKT } from 'fp-ts/lib/HKT' ; import { Monad1 } from 'fp-ts/lib/Monad' ; import { Monoid , monoidString } from 'fp-ts/lib/Monoid' ; import * as O from 'fp-ts/lib/Option' ; import { pipe } from 'fp-ts/lib/pipeable' ; import { Semigroup } from 'fp-ts/lib/Semigroup' ; import { Show } from 'fp-ts/lib/Show' ; import { Traversable1 } from 'fp-ts/lib/Traversable' ; category since export interface Nil { readonly type : 'Nil' ; readonly length : 0 ; } category since export interface Cons < A > { readonly type : 'Cons' ; readonly head : A ; readonly tail : List < A > ; readonly length : number ; } category since export type List < A > = Nil | Cons < A > ; category since export const nil = { type : 'Nil' , length : 0 } ; example category since export const cons = ( head , tail ) => ( { type : 'Cons' , head , tail , length : 1 + tail . length } ) ; example category since export const fromArray = < A > ( as ) : List < A > => A . array . reduceRight < A , List < A > > ( as , nil , cons ) ; example category since export const head = ( fa ) => ( isCons ( fa ) ? O . some ( fa . head ) : O . none ) ; example category since export const tail = ( fa ) => ( isCons ( fa ) ? O . some ( fa . tail ) : O . none ) ; example category since export const foldLeft = ( onNil , onCons ) => ( fa ) => ( isNil ( fa ) ? onNil ( ) : onCons ( fa . head , fa . tail ) ) ; example category since export const toArray = < A > ( fa ) : Array < A > => { const length = fa . length ; const out = new Array ( length ) ; let l = fa ; for ( let i = 0 ; i < length ; i ++ ) { out [ i ] = ( l as Cons < A > ) . head ; l = ( l as Cons < A > ) . tail ; } return out ; } ; example category since export const toReversedArray = < A > ( fa ) : Array < A > => { const length = fa . length ; const out = new Array ( length ) ; let l = fa ; for ( let i = 0 ; i < length ; i ++ ) { out [ length - i - 1 ] = ( l as Cons < A > ) . head ; l = ( l as Cons < A > ) . tail ; } return out ; } ; example category since export const reverse = < A > ( fa ) : List < A > => { let out = nil ; let l = fa ; while ( isCons ( l ) ) { out = cons ( l . head , out ) ; l = l . tail ; } return out ; } ; example category since export const dropLeft = ( n ) => < A > ( fa ) : List < A > => { if ( isNil ( fa ) ) return nil ; let i = 0 ; let l = fa ; while ( isCons ( l ) && i < n ) { i ++ ; l = l . tail ; } return l ; } ; example since export function dropLeftWhile < A , B extends A > ( refinement ) ; export function dropLeftWhile < A > ( predicate ) ; export function dropLeftWhile < A > ( predicate ) { return ( fa ) => { if ( isNil ( fa ) ) return nil ; let l = fa ; while ( isCons ( l ) && predicate ( l . head ) ) { l = l . tail ; } return l ; } ; } const map_ = ( fa , f ) => pipe ( fa , map ( f ) ) ; const ap_ = ( fab , fa ) => pipe ( fab , ap ( fa ) ) ; const chain_ = ( ma , f ) => pipe ( ma , chain ( f ) ) ; const reduce_ = ( fa , b , f ) => pipe ( fa , reduce ( b , f ) ) ; const reduceRight_ = ( fa , b , f ) => pipe ( fa , reduceRight ( b , f ) ) ; const foldMap_ = ( M ) => ( fa , f ) => pipe ( fa , foldMap ( M ) ( f ) ) ; const traverse_ = < F > ( F ) : ( < A , B > ( ta : List < A > , f : ( a : A ) => HKT < F , B > ) => HKT < F , List < B > > ) => { return < A , B > ( ta , f ) => list . reduceRight ( ta , F . of < List < B > > ( nil ) , ( a , fbs ) => F . ap ( F . map ( fbs , ( bs ) => ( b ) => cons ( b , bs ) ) , f ( a ) ) ) ; } ; const sequence_ = < F > ( F ) => < A > ( ta ) : HKT < F , List < A > > => { return list . reduceRight ( ta , F . of < List < A > > ( nil ) , ( a , fas ) => F . ap ( F . map ( fas , ( as ) => ( a ) => cons ( a , as ) ) , a ) ) ; } ; category since export const map = < A , B > ( f ) => ( fa ) : List < B > => pipe ( toArray ( fa ) , A . reduceRight < A , List < B > > ( nil , ( a , b ) => cons ( f ( a ) , b ) ) ) ; category since export const ap = ( fa ) => chain ( ( f ) => pipe ( fa , map ( f ) ) ) ; category since export const apFirst = ( fb ) => flow ( map ( ( a ) => ( ) => a ) , ap ( fb ) ) ; category since export const apSecond = < B > ( fb ) : ( < A > ( fa : List < A > ) => List < B > ) => flow ( map ( ( ) => ( b ) => b ) , ap ( fb ) ) ; category since export const chain = < A , B > ( f ) => ( ma ) : List < B > => pipe ( ma , foldLeft ( ( ) => nil , ( x , xs ) => { const S = getSemigroup < B > ( ) ; let out = f ( x ) ; let l = xs ; while ( isCons ( l ) ) { out = S . concat ( out , f ( l . head ) ) ; l = l . tail ; } return out ; } ) ) ; category since export const chainFirst = ( f ) => chain ( ( a ) => pipe ( f ( a ) , map ( ( ) => a ) ) ) ; category since export const reduce = ( b , f ) => ( fa ) => { let out = b ; let l = fa ; while ( isCons ( l ) ) { out = f ( out , l . head ) ; l = l . tail ; } return out ; } ; category since export const reduceRight = ( b , f ) => ( fa ) => pipe ( toArray ( fa ) , A . reduceRight ( b , f ) ) ; category since export const foldMap = ( M ) => ( f ) => ( fa ) => { let out = M . empty ; let l = fa ; while ( isCons ( l ) ) { out = M . concat ( out , f ( l . head ) ) ; l = l . tail ; } return out ; } ; category since export const sequence = < F > ( F ) : ( < A > ( ta : List < HKT < F , A > > ) => HKT < F , List < A > > ) => sequence_ ( F ) ; example category since export const of = ( head ) => cons ( head , nil ) ; example since export const findIndex = < A > ( predicate ) => ( fa ) : O . Option < number > => { let l = fa ; let i = 0 ; while ( isCons ( l ) ) { if ( predicate ( l . head ) ) return O . some ( i ) ; l = l . tail ; i ++ ; } return O . none ; } ; category since export const URI = 'List' ; category since export type URI = typeof URI ; declare module 'fp-ts/lib/HKT' { interface URItoKind < A > { List : List < A > ; } } example category since export const getEq = < A > ( E ) : Eq . Eq < List < A > > => ( { equals : ( x , y ) => { if ( x . length !== y . length ) return false ; let lx = x ; let ly = y ; while ( isCons ( lx ) && isCons ( ly ) ) { if ( ! E . equals ( lx . head , ly . head ) ) return false ; lx = lx . tail ; ly = ly . tail ; } return true ; } } ) ; category since export const getShow = < A > ( S ) : Show < List < A > > => ( { show : ( as ) => pipe ( as , map ( S . show ) , foldLeft ( ( ) => 'Nil' , ( x , xs ) => `(${ intercalate ( monoidString , Foldable ) ( ' : ' , cons ( x , xs ) ) } : Nil)` ) ) } ) ; category since export const getSemigroup = < A > ( ) : Semigroup < List < A > > => ( { concat : ( xs , ys ) => pipe ( xs , reduceRight ( ys , cons ) ) } ) ; category since export const getMonoid = < A > ( ) : Monoid < List < A > > => ( { ... getSemigroup ( ) , empty : nil } ) ; category since export const Functor = { URI , map : map_ } ; category since export const Apply = { URI , map : map_ , ap : ap_ } ; category since export const Applicative = { URI , map : map_ , ap : ap_ , of } ; category since export const Monad = { URI , map : map_ , ap : ap_ , of , chain : chain_ } ; category since export const Foldable = { URI , foldMap : foldMap_ , reduce : reduce_ , reduceRight : reduceRight_ } ; category since export const Traversable = { URI , map : map_ , foldMap : foldMap_ , reduce : reduce_ , reduceRight : reduceRight_ , traverse : traverse_ , sequence : sequence_ } ; category since export const list = { URI , map : map_ , reduce : reduce_ , foldMap : foldMap_ , reduceRight : reduceRight_ , traverse : traverse_ , sequence : sequence_ } ; internal const bind_ = < A , N extends string , B > ( a , name , b ) : { [ K in keyof A | N ] : K extends keyof A ? A [ K ] : B ; } => Object . assign ( { } , a , { [ name ] : b } ) as any ; since export const bindTo = < N extends string > ( name ) => < A > ( fa ) : List < { [ K in N ] : A ; } > => pipe ( fa , map ( ( a ) => bind_ ( { } , name , a ) ) ) ; since export const bind = < N extends string , A , B > ( name , f ) => ( fa ) : List < { [ K in keyof A | N ] : K extends keyof A ? A [ K ] : B ; } > => pipe ( fa , chain ( ( a ) => pipe ( f ( a ) , map ( ( b ) => bind_ ( a , name , b ) ) ) ) ) ; since export const apS = < A , N extends string , B > ( name , fb ) : ( ( fa : List < A > ) => List < { [ K in keyof A | N ] : K extends keyof A ? A [ K ] : B ; } > ) => flow ( map ( ( a ) => ( b ) => bind_ ( a , name , b ) ) , ap ( fb ) ) ; example since export const isNil = < A > ( a ) : a is Nil => a . type === 'Nil' ; example since export const isCons = < A > ( a ) : a is Cons < A > => a . type === 'Cons' ;