Nuprl Theory List

(only non hidden objects are presented)

COMList_ancestorsoperator
MLList_load_refload_hthy "List" ;;
COMList_Nuprl_defs--------------
THMiff_asserts_iff_eq_boolsp,q:. (p q) p = q
MLhol_type_inf_hackadd_get_type_top_level_hook `hol_type_inf_hack` (\T. hn T) ;;
MLreduce_list_indadd_simp (`reduce_list_ind`, `list_ind`, (\e t. true), RedexC) ;;
DISPsnoc_dfsnoc(<x:x:*><l:l:*>)== snoc(<x><l>)
MLsnoc_mlsnoc(x;l)==r if null(l) then x::[] else head(l)::snoc(x;tl(l)) fi
MLsnoc_simpadd_rec_simp [snoc(x;[]); snoc(x;y::l)] ;;
THMsnoc_wf'a:S. x:'a. l:'a List. snoc(x;l) 'a List
DISPfoldr_dffoldr(<f:f:*><e:e:*><l:l:*>)== foldr(<f><e><l>)
MLfoldr_mlfoldr(f;e;l)==r if null(l) then e else f head(l) foldr(f;e;tl(l)) fi
MLfoldr_simpadd_rec_simp [foldr(f;e;[]); foldr(f;e;x::l)] ;;
THMfoldr_wf'a,'b:S. f:'a 'b 'b. e:'b. l:'a List. foldr(f;e;l) 'b
DISPfoldl_dffoldl(<f:f:*><e:e:*><l:l:*>)== foldl(<f><e><l>)
MLfoldl_mlfoldl(f;e;l)==r if null(l) then e else foldl(f;f e head(l);tl(l)) fi
MLfoldl_simpadd_rec_simp [foldl(f;e;[]); foldl(f;e;x::l)] ;;
THMfoldl_wf'a,'b:S. f:'b 'a 'b. e:'b. l:'a List. foldl(f;e;l) 'b
DISPfilter_dffilter(<P:P:*><l:l:*>)== filter(<P><l>)
MLfilter_mlfilter(P;l) ==r if null(l) then [] else if P head(l) then head(l)::filter(P;tl(l)) else filter(P;tl(l)) fi fi
MLfilter_simpadd_rec_simp [filter(P;[]); filter(P;x::l)] ;;
THMfilter_wf'a:S. P:'a . l:'a List. filter(P;l) 'a List
DISPscanl_dfscanl(<f:f:*><e:e:*><l:l:*>)== scanl(<f><e><l>)
MLscanl_mlscanl(f;e;l) ==r if null(l) then e::[] else e::scanl(f;f e head(l);tl(l)) fi
MLscanl_simpadd_rec_simp [scanl(f;e;[]); scanl(f;e;x::l)] ;;
THMscanl_wf'a,'b:S. f:'b 'a 'b. e:'b. l:'a List. scanl(f;e;l) 'b List
DISPscanr_dfscanr(<f:f:*><e:e:*><l:l:*>)== scanr(<f><e><l>)
MLscanr_mlscanr(f;e;l) ==r if null(l) then e::[] else (f head(l) head(scanr(f;e;tl(l))))::scanr(f;e;tl(l)) fi
MLscanr_simpadd_rec_simp [scanr(f;e;[]); scanr(f;e;x::l)] ;;
THMscanr_wf'a,'b:S. f:'a 'b 'b. e:'b. l:'a List. scanr(f;e;l) 'b List
MLreverse_simpadd_rec_simp [rev([]); rev(x::l)] ;;
DISPsome_dfsome(<P:P:*><l:l:*>)== some(<P><l>)
MLsome_mlsome(P;l)==r if null(l) then ff else (P head(l)) some(P;tl(l)) fi
MLsome_simpadd_rec_simp [some(P;[]); some(P;x::l)] ;;
THMsome_wf'a:S. P:'a . l:'a List. some(P;l)
DISPis_el_dfParens ::Prec(atomrel):: {->0}<t:term>{<-}{\\? }_{<eq:eq_pred>} {->0}<l:list>{<-} == <t> _{<eq>} <l>
ABSis_elx _{f} l == some(f x;l)
THMis_el_wf'a:S. f:eq('a). x:'a. l:'a List. (x _{f} l)
DISPand_el_dfand_el(<l:l:*>)== and_el(<l>)
ABSand_eland_el(l) == every(Id;l)
THMand_el_wfl: List. and_el(l)
MLand_el_mladd_matching_simp [and_el([]);and_el(x::l)] (UnfoldTopAbC ANDTHENC Simp1C ANDTHENC FoldTopC `and_el`) ;;
DISPor_el_dfor_el(<l:l:*>)== or_el(<l>)
ABSor_elor_el(l) == some(Id;l)
THMor_el_wfl: List. or_el(l)
MLor_el_mladd_matching_simp [or_el([]);or_el(x::l)] (UnfoldTopAbC ANDTHENC Simp1C ANDTHENC FoldTopC `or_el`) ;;
DISPseg_dfseg(<m:m:*><n:n:*><l:l:*>)== seg(<m><n><l>)
MLseg_mlseg(m;n;l) ==r if null(l) (m = 0) then [] else if (n = 0) then head(l)::seg(m - 1;n;tl(l)) else seg(m;n - 1;tl(l)) fi fi
THMseg_wf'a:S. m,n:. l:'a List. seg(m;n;l) 'a List
DISPlast_el_dflast_el(<l:l:*>)== last_el(<l>)
ABSlast_ellast_el(l) == head(seg(1;pre(||l||);l))
THMlast_el_wf'a:S. l:'a List. mt(l) last_el(l) 'a
DISPbut_last_el_dfbut_last_el(<l:l:*>)== but_last_el(<l>)
ABSbut_last_elbut_last_el(l) == seg(pre(||l||);0;l)
THMbut_last_el_wf'a:S. l:'a List. but_last_el(l) 'a List
DISPbutlastn_dfbutlastn(<n:n:*><l:l:*>)== butlastn(<n><l>)
ABSbutlastnbutlastn(n;l) == rev(nth_tl(n;rev(l)))
THMbutlastn_wf'a:S. n:. l:'a List. butlastn(n;l) 'a List
DISPlastn_dflastn(<n:n:*><l:l:*>)== lastn(<n><l>)
THMnot_mt_if_pos_length'a:. l:'a List. 0 < ||l|| (mt(l) True)
MLnot_mt_if_pos_length_lsimpadd_cond_lemma_simp `not_mt_if_pos_length` [Trivial] ;;
ABSlastnlastn(n;l) == rev(firstn(n;rev(l)))
DISPell_dfell(<n:n:*><l:l:*>)== ell(<n><l>)
MLell_mlell(n;l) ==r if (n = 0) then last_el(l) else ell(n - 1;but_last_el(l)) fi
THMell_wf'a:S. n:. l:'a List. n < ||l|| ell(n;l) 'a
THMlastn_wf'a:S. n:. l:'a List. lastn(n;l) 'a List
DISPis_prefix_dfis_prefix(<f:f:*><l1:l1:*><l2:l2:*>)== is_prefix(<f><l1><l2>)
MLis_prefix_mlis_prefix(f;l1;l2) ==r null(l2) if null(l1) then ff else f head(l1) head(l2) is_prefix(f;tl(l1);tl(l2)) fi
MLis_prefix_simpadd_rec_simp [is_prefix(f;l;[]); is_prefix(f;x::y;x'::y'); is_prefix(f;[];x::y); is_prefix(f;x::y;[])] ;;
THMis_prefix_wf'a:S. f:eq('a). l1,l2:'a List. is_prefix(f;l1;l2)
DISPis_suffix_dfis_suffix(<f:f:*><l1:l1:*><l2:l2:*>)== is_suffix(<f><l1><l2>)
ABSis_suffixis_suffix(f;l1;l2) == is_prefix(f;rev(l1);rev(l2))
MLis_suffix_simpadd_matching_simp [is_suffix(f;l;[]); is_suffix(f;x::y;x'::y'); is_suffix(f;[];x::y); is_suffix(f;x::y;[])] UnfoldTopAbC ;;
THMis_suffix_wf'a:S. f:eq('a). l1,l2:'a List. is_suffix(f;l1;l2)
DISPis_sublist_dfis_sublist(<f:f:*><l1:l1:*><l2:l2:*>)== is_sublist(<f><l1><l2>)
MLis_sublist_mlis_sublist(f;l1;l2) ==r null(l2) if null(l1) then ff else (f head(l1) head(l2) is_prefix(f;tl(l1);tl(l2))) is_sublist(f;tl(l1);l2) fi
MLis_sublist_simpadd_rec_simp [is_sublist(f;[];[]); is_sublist(f;x::y;x'::y'); is_sublist(f;[];x::y); is_sublist(f;x::y;[])] ;;
THMis_sublist_wf'a:S. f:eq('a). l1,l2:'a List. is_sublist(f;l1;l2)
DISPsplitp_dfsplitp(<P:P:*><l:l:*>)== splitp(<P><l>)
MLsplitp_mlsplitp(P;l) ==r if null(l) then <[], []> else if P head(l) then <[], l> else let <l1,l2> = splitp(P;tl(l)) in <head(l)::l1, l2> fi fi
MLsplitp_simpadd_rec_simp [splitp(P;[]); splitp(P;x::l)] ;;
THMsplitp_wf'a:S. P:'a . l:'a List. splitp(P;l) 'a List 'a List
DISPprefix_dfprefix(<P:P:*><l:l:*>)== prefix(<P><l>)
ABSprefixprefix(P;l) == splitp((b:. b) o P;l).1
THMprefix_wf'a:S. P:'a . l:'a List. prefix(P;l) 'a List
DISPsuffix_dfsuffix(<P:P:*><l:l:*>)== suffix(<P><l>)
ABSsuffixsuffix(P;l) == foldl(l',x.if P x then snoc(x;l') else [] fi ;[];l)
THMsuffix_wf'a:S. P:'a . l:'a List. suffix(P;l) 'a List
DISPzip_dfzip(<l:l:*><l':l':*>)== zip(<l><l'>)
MLzip_mlzip(l;l') ==r if null(l) then [] else if null(l') then [] else <head(l), head(l')>::zip(tl(l);tl(l')) fi fi
MLzip_simpadd_rec_simp [zip([];l'); zip(x:::l;[]); zip(x:::l;x'::l')] ;;
THMzip_wf'a,'b:S. l:'a List. l':'b List. zip(l;l') ('a 'b) List
DISPunzip_dfunzip(<l:l:*>)== unzip(<l>)
MLunzip_mlunzip(l) ==r if null(l) then <[], []> else let <x,y> = head(l) in <x::(unzip(tl(l)).1), y::(unzip(tl(l)).2)> fi
MLunzip_simpadd_rec_simp [unzip([]); unzip(<x, y>::l)] ;;
THMunzip_wf'a,'b:S. l:('a 'b) List. unzip(l) 'a List 'b List
DISPunzip_fst_dfunzip_fst(<l:l:*>)== unzip_fst(<l>)
ABSunzip_fstunzip_fst(l) == unzip(l).1
THMunzip_fst_wf'a,'b:S. l:('a 'b) List. unzip_fst(l) 'a List
DISPunzip_snd_dfunzip_snd(<l:l:*>)== unzip_snd(<l>)
ABSunzip_sndunzip_snd(l) == unzip(l).2
THMunzip_snd_wf'a,'b:S. l:('a 'b) List. unzip_snd(l) 'b List
DISPgenlist_dfgenlist(<f:f:*><n:n:*>)== genlist(<f><n>)
MLgenlist_mlgenlist(f;n) ==r if (n = 0) then [] else (f (n - 1))::genlist(f;n - 1) fi
THMgenlist_wf'a:S. f: 'a. n:. genlist(f;n) 'a List
DISPreplicate_dfreplicate(<n:n:*><x:x:*>)== replicate(<n><x>)
MLreplicate_mlreplicate(n;x)==r if (n = 0) then [] else x::replicate(n - 1;x) fi
THMreplicate_wf'a:S. n:. x:'a. replicate(n;x) 'a List
COMList_Nuprl_aux--------------
COMList_HOL_type_defs--------------
COMList_HOL_const_defs--------------
DISPhsnoc_dfsnoc== snoc
ABShsnocsnoc == x:'a. l:'a List. snoc(x;l)
MLhsnoc_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hsnoc");; add_info `dire ct_new_hdef` `hsnoc`;;
DISPhfoldr_dffoldr== foldr
ABShfoldrfoldr == f:'a 'b 'b. e:'b. l:'a List. foldr(f;e;l)
MLhfoldr_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hfoldr");; add_info `dir ect_new_hdef` `hfoldr`;;
DISPhfoldl_dffoldl== foldl
ABShfoldlfoldl == f:'b 'a 'b. e:'b. l:'a List. foldl(f;e;l)
MLhfoldl_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hfoldl");; add_info `dir ect_new_hdef` `hfoldl`;;
MLhfoldl_simpadd_rec_simp [foldl(f;e;[]); foldl(f;e;x::l)] ;;
DISPhfilter_dffilter== filter
ABShfilterfilter == P:'a . l:'a List. filter(P;l)
MLhfilter_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hfilter");; add_info `di rect_new_hdef` `hfilter`;;
DISPhscanl_dfscanl== scanl
ABShscanlscanl == f:'b 'a 'b. e:'b. l:'a List. scanl(f;e;l)
MLhscanl_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hscanl");; add_info `dir ect_new_hdef` `hscanl`;;
DISPhscanr_dfscanr== scanr
ABShscanrscanr == f:'a 'b 'b. e:'b. l:'a List. scanr(f;e;l)
MLhscanr_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hscanr");; add_info `dir ect_new_hdef` `hscanr`;;
DISPhreverse_dfreverse== reverse
ABShreversereverse == l:'a List. rev(l)
MLhreverse_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hreverse");; add_info `d irect_old_hdef` `hreverse`;;
DISPhall_el_dfall_el== all_el
ABShall_elall_el == P:'a . l:'a List. every(P;l)
MLhall_el_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hall_el");; add_info `di rect_old_hdef` `hall_el`;;
DISPhsome_el_dfsome_el== some_el
ABShsome_elsome_el == P:'a . l:'a List. some(P;l)
MLhsome_el_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hsome_el");; add_info `d irect_new_hdef` `hsome_el`;;
DISPhis_el_dfis_el== is_el
ABShis_elis_el == x:'a. l:'a List. x _{<eq_pred:(x:'a. y:'a. x = y)>} l
MLhis_el_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "his_el");; add_info `dir ect_new_hdef` `his_el`;;
DISPhand_el_dfand_el== and_el
ABShand_eland_el == l: List. and_el(l)
MLhand_el_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hand_el");; add_info `di rect_new_hdef` `hand_el`;;
DISPhor_el_dfor_el== or_el
ABShor_elor_el == l: List. or_el(l)
MLhor_el_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hor_el");; add_info `dir ect_new_hdef` `hor_el`;;
DISPhfirstn_dffirstn== firstn
ABShfirstnfirstn == n:. l:'a List. firstn(n;l)
MLhfirstn_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hfirstn");; add_info `di rect_old_hdef` `hfirstn`;;
DISPhbutfirstn_dfbutfirstn== butfirstn
ABShbutfirstnbutfirstn == n:. l:'a List. nth_tl(n;l)
MLhbutfirstn_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hbutfirstn");; add_info `direct_old_hdef` `hbutfirstn`;;
DISPhseg_dfseg== seg
ABShsegseg == m:. n:. l:'a List. seg(m;n;l)
MLhseg_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hseg");; add_info `direc t_new_hdef` `hseg`;;
DISPhlast_dflast== last
ABShlastlast == l:'a List. if null(l) then arb('a) else last_el(l) fi
THMhlast_nuprl'a:S. l:'a List. mt(l) last l = last_el(l)
MLhlast_mladd_info `dead_hdef` `hlast`;; add_to_simpset `hol_to_nuprl` (lemma_to_cond_simp `hlast_nuprl` []) ;;
DISPhbutlast_dfbutlast== butlast
ABShbutlastbutlast == l:'a List. but_last_el(l)
MLhbutlast_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hbutlast");; add_info `d irect_new_hdef` `hbutlast`;;
DISPhlastn_dflastn== lastn
ABShlastnlastn == n:. l:'a List. lastn(n;l)
MLhlastn_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hlastn");; add_info `dir ect_old_hdef` `hlastn`;;
DISPhbutlastn_dfbutlastn== butlastn
ABShbutlastnbutlastn == n:. l:'a List. butlastn(n;l)
MLhbutlastn_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hbutlastn");; add_info ` direct_new_hdef` `hbutlastn`;;
DISPhell_dfell== ell
ABShellell == n:. l:'a List. if n <z ||l|| then ell(n;l) else arb('a) fi
THMhell_nuprl'a:S. n:. l:'a List. n < ||l|| ell n l = ell(n;l)
MLhell_mladd_info `dead_hdef` `hell`;; add_to_simpset `hol_to_nuprl` (lemma_to_cond_simp `hell_nuprl` []) ;;
DISPhis_prefix_dfis_prefix== is_prefix
ABShis_prefixis_prefix == l1:'a List. l2:'a List. is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
MLhis_prefix_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "his_prefix");; add_info `direct_new_hdef` `his_prefix`;;
DISPhis_suffix_dfis_suffix== is_suffix
ABShis_suffixis_suffix == l1:'a List. l2:'a List. is_suffix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
MLhis_suffix_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "his_suffix");; add_info `direct_new_hdef` `his_suffix`;;
DISPhis_sublist_dfis_sublist== is_sublist
ABShis_sublistis_sublist == l1:'a List. l2:'a List. is_sublist(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
MLhis_sublist_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "his_sublist");; add_info `direct_new_hdef` `his_sublist`;;
DISPhsplitp_dfsplitp== splitp
ABShsplitpsplitp == P:'a . l:'a List. splitp(P;l)
MLhsplitp_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hsplitp");; add_info `di rect_new_hdef` `hsplitp`;;
DISPhprefix_dfprefix== prefix
ABShprefixprefix == P:'a . l:'a List. prefix(P;l)
MLhprefix_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hprefix");; add_info `di rect_new_hdef` `hprefix`;;
DISPhsuffix_dfsuffix== suffix
ABShsuffixsuffix == P:'a . l:'a List. suffix(P;l)
MLhsuffix_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hsuffix");; add_info `di rect_new_hdef` `hsuffix`;;
DISPhzip_dfzip== zip
ABShzipzip == ll:'a List 'b List. let <l,l'> = ll in zip(l;l')
MLhzip_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hzip");; add_info `direc t_new_hdef` `hzip`;;
DISPhunzip_dfunzip== unzip
ABShunzipunzip == l:('a 'b) List. unzip(l)
MLhunzip_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hunzip");; add_info `dir ect_new_hdef` `hunzip`;;
DISPhunzip_fst_dfunzip_fst== unzip_fst
ABShunzip_fstunzip_fst == l:('a 'b) List. unzip_fst(l)
MLhunzip_fst_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hunzip_fst");; add_info `direct_new_hdef` `hunzip_fst`;;
DISPhunzip_snd_dfunzip_snd== unzip_snd
ABShunzip_sndunzip_snd == l:('a 'b) List. unzip_snd(l)
MLhunzip_snd_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hunzip_snd");; add_info `direct_new_hdef` `hunzip_snd`;;
DISPhgenlist_dfgenlist== genlist
ABShgenlistgenlist == f: 'a. n:. rev(genlist(f;n))
MLhgenlist_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hgenlist");; add_info `d irect_new_hdef` `hgenlist`;;
DISPhreplicate_dfreplicate== replicate
ABShreplicatereplicate == n:. x:'a. replicate(n;x)
MLhreplicate_mladd_to_simpset `hol_to_nuprl` (hdef_to_simp "hreplicate");; add_info `direct_new_hdef` `hreplicate`;;
COMList_HOL_obligations--------------
THMhsnoc_wf'a:S. snoc 'a hlist{}('a) hlist{}('a)
THMhfoldr_wf'a,'b:S. foldr ('a 'b 'b) 'b hlist{}('a) 'b
THMhfoldl_wf'b,'a:S. foldl ('b 'a 'b) 'b hlist{}('a) 'b
THMhfilter_wf'a:S. filter ('a hbool{}) hlist{}('a) hlist{}('a)
THMhscanl_wf'b,'a:S. scanl ('b 'a 'b) 'b hlist{}('a) hlist{}('b)
THMhscanr_wf'a,'b:S. scanr ('a 'b 'b) 'b hlist{}('a) hlist{}('b)
THMhreverse_wf'a:S. reverse hlist{}('a) hlist{}('a)
THMhall_el_wf'a:S. all_el ('a hbool{}) hlist{}('a) hbool{}
THMhsome_el_wf'a:S. some_el ('a hbool{}) hlist{}('a) hbool{}
THMhis_el_wf'a:S. is_el 'a hlist{}('a) hbool{}
THMhand_el_wfand_el hlist{}(hbool{}) hbool{}
THMhor_el_wfor_el hlist{}(hbool{}) hbool{}
THMhfirstn_wf'a:S. firstn hnum{} hlist{}('a) hlist{}('a)
THMhbutfirstn_wf'a:S. butfirstn hnum{} hlist{}('a) hlist{}('a)
THMhseg_wf'a:S. seg hnum{} hnum{} hlist{}('a) hlist{}('a)
THMhlast_wf'a:S. last hlist{}('a) 'a
THMhbutlast_wf'a:S. butlast hlist{}('a) hlist{}('a)
THMhlastn_wf'a:S. lastn hnum{} hlist{}('a) hlist{}('a)
THMhbutlastn_wf'a:S. butlastn hnum{} hlist{}('a) hlist{}('a)
THMhell_wf'a:S. ell hnum{} hlist{}('a) 'a
THMhis_prefix_wf'a:S. is_prefix hlist{}('a) hlist{}('a) hbool{}
THMhis_suffix_wf'a:S. is_suffix hlist{}('a) hlist{}('a) hbool{}
THMhis_sublist_wf'a:S. is_sublist hlist{}('a) hlist{}('a) hbool{}
THMhsplitp_wf'a:S splitp ('a hbool{}) hlist{}('a) hprod{}(hlist{}('a); hlist{}('a))
THMhprefix_wf'a:S. prefix ('a hbool{}) hlist{}('a) hlist{}('a)
THMhsuffix_wf'a:S. suffix ('a hbool{}) hlist{}('a) hlist{}('a)
THMhzip_wf'a,'b:S. zip hprod{}(hlist{}('a); hlist{}('b)) hlist{}(hprod{}('a; 'b))
THMhunzip_wf'a,'b:S. unzip hlist{}(hprod{}('a; 'b)) hprod{}(hlist{}('a); hlist{}('b))
THMhunzip_fst_wf'a,'b:S. unzip_fst hlist{}(hprod{}('a; 'b)) hlist{}('a)
THMhunzip_snd_wf'a,'b:S. unzip_snd hlist{}(hprod{}('a; 'b)) hlist{}('b)
THMhgenlist_wf'a:S. genlist (hnum{} 'a) hnum{} hlist{}('a)
THMhreplicate_wf'a:S. replicate hnum{} 'a hlist{}('a)
THMhsnoc_wd'a:S (and (all (x:'a. equal (snoc x nil) (cons x nil))) (all (x:'a. all (x':'a. all (l:hlist{}('a). equal (snoc x (cons x' l)) (cons x' (snoc x l)))))))
THMhfoldr_wd'a,'b:S. (and (all (f:'a 'b 'b. all (e:'b. equal (foldr f e nil) e))) (all (f:'a 'b 'b. all (e:'b. all (x:'a. all (l:hlist{}('a). equal (foldr f e (cons x l)) (f x (foldr f e l))))))))
THMhfoldl_wd'b,'a:S. (and (all (f:'b 'a 'b. all (e:'b. equal (foldl f e nil) e))) (all (f:'b 'a 'b. all (e:'b. all (x:'a. all (l:hlist{}('a). equal (foldl f e (cons x l)) (foldl f (f e x) l)))))))
THMhfilter_wd'a:S (and (all (P:'a hbool{}. equal (filter P nil) nil)) (all (P:'a hbool{}. all (x:'a. all (l:hlist{}('a). equal (filter P (cons x l)) (cond (P x) (cons x (filter P l)) (filter P l)))))))
THMhscanl_wd'b,'a:S. (and (all (f:'b 'a 'b. all (e:'b. equal (scanl f e nil) (cons e nil)))) (all (f:'b 'a 'b. all (e:'b. all (x:'a. all (l:hlist{}('a). equal (scanl f e (cons x l)) (cons e (scanl f (f e x) l))))))))
THMhscanr_wd'a,'b:S. (and (all (f:'a 'b 'b. all (e:'b. equal (scanr f e nil) (cons e nil)))) (all (f:'a 'b 'b. all (e:'b. all (x:'a. all (l:hlist{}('a). equal (scanr f e (cons x l)) (cons (f x (hd (scanr f e l))) (scanr f e l))))))))
THMreverse_snoc_lemma'a:S. x:'a. l:'a List. snoc(x;l) = l @ (x::[])
THMhreverse_wd'a:S (and (equal (reverse nil) nil) (all (x:'a. all (l:hlist{}('a). equal (reverse (cons x l)) (snoc x (reverse l))))))
THMhall_el_wd'a:S (and (all (P:'a hbool{}. equal (all_el P nil) t)) (all (P:'a hbool{}. all (x:'a. all (l:hlist{}('a). equal (all_el P (cons x l)) (and (P x) (all_el P l)))))))
THMhsome_el_wd'a:S (and (all (P:'a hbool{}. equal (some_el P nil) f)) (all (P:'a hbool{}. all (x:'a. all (l:hlist{}('a). equal (some_el P (cons x l)) (or (P x) (some_el P l)))))))
THMhis_el_def'a:S (all (x:'a. all (l:hlist{}('a). equal (is_el x l) (some_el (equal x) l))))
THMhand_el_def(equal and_el (all_el i))
THMhor_el_def(equal or_el (some_el i))
THMhfirstn_wd'a:S (and (all (l:hlist{}('a). equal (firstn 0 l) nil)) (all (n:hnum{}. all (x:'a. all (l:hlist{}('a). equal (firstn (suc n) (cons x l)) (cons x (firstn n l)))))))
THMhbutfirstn_wd'a:S (and (all (l:hlist{}('a). equal (butfirstn 0 l) l)) (all (n:hnum{}. all (x:'a. all (l:hlist{}('a). equal (butfirstn (suc n) (cons x l)) (butfirstn n l))))))
THMhseg_wd'a:S (and (all (k:hnum{}. all (l:hlist{}('a). equal (seg 0 k l) nil))) (and (all (m:hnum{}. all (x:'a. all (l:hlist{}('a). equal (seg (suc m) 0 (cons x l)) (cons x (seg m 0 l)))))) (all (m:hnum{}. all (k:hnum{}. all (x:'a. all (l:hlist{}('a). equal (seg (suc m) (suc k) (cons x l)) (seg (suc m) k l))))))))
THMhlast_def'a:S (all (l:hlist{}('a). equal (last l) (hd (seg 1 (pre (length l)) l))))
THMhbutlast_def'a:S (all (l:hlist{}('a). equal (butlast l) (seg (pre (length l)) 0 l)))
THMhlastn_wd'a:S (and (all (l:hlist{}('a). equal (lastn 0 l) nil)) (all (n:hnum{}. all (x:'a. all (l:hlist{}('a). equal (lastn (suc n) (snoc x l)) (snoc x (lastn n l)))))))
THMhbutlastn_wd'a:S (and (all (l:hlist{}('a). equal (butlastn 0 l) l)) (all (n:hnum{}. all (x:'a. all (l:hlist{}('a). equal (butlastn (suc n) (snoc x l)) (butlastn n l))))))
THMhell_wd'a:S (and (all (l:hlist{}('a). equal (ell 0 l) (last l))) (all (n:hnum{}. all (l:hlist{}('a). equal (ell (suc n) l) (ell n (butlast l))))))
MLreverse_append_simpadd_lemma_simp `reverse_append` ;;
MLand_or_simpsmap add_lemma_simp ``and_true true_and and_false false_and or_true true_or or_false false_or`` ;;
THMhis_prefix_wd'a:S (and (all (l:hlist{}('a). equal (is_prefix l nil) t)) (and (all (x:'a. all (l:hlist{}('a). equal (is_prefix nil (cons x l)) f))) (all (x1:'a. all (l1:hlist{}('a). all (x2:'a. all (l2:hlist{}('a). equal (is_prefix (cons x1 l1) (cons x2 l2)) (and (equal x1 x2) (is_prefix l1 l2)))))))))
THMhis_suffix_wd'a:S (and (all (l:hlist{}('a). equal (is_suffix l nil) t)) (and (all (x:'a. all (l:hlist{}('a). equal (is_suffix nil (snoc x l)) f))) (all (x1:'a. all (l1:hlist{}('a). all (x2:'a. all (l2:hlist{}('a). equal (is_suffix (snoc x1 l1) (snoc x2 l2)) (and (equal x1 x2) (is_suffix l1 l2)))))))))
THMhis_sublist_wd'a:S (and (all (l:hlist{}('a). equal (is_sublist l nil) t)) (and (all (x:'a. all (l:hlist{}('a). equal (is_sublist nil (cons x l)) f))) (all (x1:'a. all (l1:hlist{}('a). all (x2:'a. all (l2:hlist{}('a). equal (is_sublist (cons x1 l1) (cons x2 l2)) (or (and (equal x1 x2) (is_prefix l1 l2)) (is_sublist l1 (cons x2 l2))))))))))
THMhsplitp_wd'a:S (and (all (P:'a hbool{}. equal (splitp P nil) (pair nil nil))) (all (P:'a hbool{}. all (x:'a. all (l:hlist{}('a). equal (splitp P (cons x l)) (cond (P x) (pair nil (cons x l)) (pair (cons x (fst (splitp P l))) (snd (splitp P l)))))))))
THMhprefix_def'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (prefix P l) (fst (splitp (o not P) l)))))
MLspread_simpadd_simp (`spread2`, `spread`, (\e t. is_spread_term t & is_pair_term (subterm t 1)), RedexC ) ;;
THMhsuffix_def'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (suffix P l) (foldl (l':hlist{}('a). x:'a. cond (P x) (snoc x l') nil) nil l))))
THMhzip_wd'a,'b:S. (and (equal (zip (pair nil nil)) nil) (all (x1:'a. all (l1:hlist{}('a). all (x2:'b. all (l2:hlist{}('b). equal (zip (pair (cons x1 l1) (cons x2 l2))) (cons (pair x1 x2) (zip (pair l1 l2)))))))))
THMhunzip_wd'a,'b:S. (and (equal (unzip nil) (pair nil nil)) (all (x:hprod{}('a; 'b). all (l:hlist{}(hprod{}('a; 'b)). equal (unzip (cons x l)) (pair (cons (fst x) (fst (unzip l))) (cons (snd x) (snd (unzip l))))))))
THMhunzip_fst_def'a,'b:S. (all (l:hlist{}(hprod{}('a; 'b)). equal (unzip_fst l) (fst (unzip l))))
THMhunzip_snd_def'a,'b:S. (all (l:hlist{}(hprod{}('a; 'b)). equal (unzip_snd l) (snd (unzip l))))
THMhgenlist_wd'a:S (and (all (f:hnum{} 'a. equal (genlist f 0) nil)) (all (f:hnum{} 'a. all (n:hnum{}. equal (genlist f (suc n)) (snoc (f n) (genlist f n))))))
THMhreplicate_wd'a:S (and (all (x:'a. equal (replicate 0 x) nil)) (all (n:hnum{}. all (x:'a. equal (replicate (suc n) x) (cons x (replicate n x))))))
COMList_HOL_theorems--------------
THMhlist_induct_2'a:S (all (P:hlist{}('a) hbool{}. implies (and (P nil) (all (l:hlist{}('a). implies (P l) (all (x:'a. P (cons x l)))))) (all (l:hlist{}('a). P l))))
THMhnull_def_2'a:S (and (equal (null nil) t) (all (x:'a. all (l:hlist{}('a). equal (null (cons x l)) f))))
THMhhd_wd_2'a:S. (all (x:'a. all (l:hlist{}('a). equal (hd (cons x l)) x)))
THMhtl_wd_2'a:S. (all (x:'a. all (l:hlist{}('a). equal (tl (cons x l)) l)))
THMhappend_wd_2'a:S (and (all (l:hlist{}('a). equal (append nil l) l)) (all (l1:hlist{}('a). all (l2:hlist{}('a). all (x:'a. equal (append (cons x l1) l2) (cons x (append l1 l2)))))))
THMhflat_wd_2'a:S (and (equal (flat nil) nil) (all (x:hlist{}('a). all (l:hlist{}(hlist{}('a)). equal (flat (cons x l)) (append x (flat l))))))
THMhlength_wd_2'a:S (and (equal (length nil) 0) (all (x:'a. all (l:hlist{}('a). equal (length (cons x l)) (suc (length l))))))
THMhmap_wd_2'a,'b:S. (and (all (f:'a 'b. equal (map f nil) nil)) (all (f:'a 'b. all (x:'a. all (l:hlist{}('a). equal (map f (cons x l)) (cons (f x) (map f l)))))))
THMhmap2_wd_2'a,'b,'c:S. (and (all (f:'a 'b 'c. equal (map2 f nil nil) nil)) (all (f:'a 'b 'c. all (x1:'a. all (l1:hlist{}('a). all (x2:'b. all (l2:hlist{}('b). equal (map2 f (cons x1 l1) (cons x2 l2)) (cons (f x1 x2) (map2 f l1 l2)))))))))
THMhel_wd_2'a:S (and (all (l:hlist{}('a). equal (el 0 l) (hd l))) (all (n:hnum{}. all (l:hlist{}('a). equal (el (suc n) l) (el n (tl l))))))
THMhsum_els_wd_2(and (equal (it_sum nil) 0) (all (x:hnum{}. all (l:hlist{}(hnum{}). equal (it_sum (cons x l)) (add x (it_sum l))))))
THMhnull_char_2'a:S (and (null nil) (all (x:'a. all (l:hlist{}('a). not (null (cons x l))))))
THMhlist_cases_2'a:S (all (l:hlist{}('a). or (equal l nil) (exists (l':hlist{}('a). exists (x:'a. equal l (cons x l'))))))
THMhcons_11_2'a:S (all (x:'a. all (l:hlist{}('a). all (x':'a. all (l':hlist{}('a). equal (equal (cons x l) (cons x' l')) (and (equal x x') (equal l l')))))))
THMhnot_nil_cons_2'a:S (all (x:'a. all (l:hlist{}('a). not (equal nil (cons x l)))))
THMhnot_cons_nil_2'a:S (all (x:'a. all (l:hlist{}('a). not (equal (cons x l) nil))))
THMhlist_not_eq_2'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). implies (not (equal l1 l2)) (all (x1:'a. all (x2:'a. not (equal (cons x1 l1) (cons x2 l2))))))))
THMhnot_eq_list_2'a:S (all (x1:'a. all (x2:'a. implies (not (equal x1 x2)) (all (l1:hlist{}('a). all (l2:hlist{}('a). not (equal (cons x1 l1) (cons x2 l2))))))))
THMheq_list_2'a:S (all (x1:'a. all (x2:'a. implies (equal x1 x2) (all (l1:hlist{}('a). all (l2:hlist{}('a). implies (equal l1 l2) (equal (cons x1 l1) (cons x2 l2))))))))
THMhcons_wd_2'a:S (all (l:hlist{}('a). implies (not (null l)) (equal (cons (hd l) (tl l)) l)))
THMhappend_assoc_3'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). all (l3:hlist{}('a). equal (append l1 (append l2 l3)) (append (append l1 l2) l3)))))
THMhlength_append_3'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (length (append l1 l2)) (add (length l1) (length l2)))))
THMhmap_append_3'a,'b:S. (all (f:'a 'b. all (l1:hlist{}('a). all (l2:hlist{}('a). equal (map f (append l1 l2)) (append (map f l1) (map f l2))))))
THMhlength_map_2'b,'a:S. (all (l:hlist{}('a). all (f:'a 'b. equal (length (map f l)) (length l))))
THMhlength_nil_3'a:S (all (l:hlist{}('a). equal (equal (length l) 0) (equal l nil)))
THMhlength_cons_3'a:S (all (l:hlist{}('a). all (n:hnum{}. equal (equal (length l) (suc n)) (exists (x:'a. exists (l':hlist{}('a). and (equal (length l') n) (equal l (cons x l'))))))))
THMhlength_eq_nil_2'a:S (all (P:hlist{}('a) hbool{}. equal (all (l:hlist{}('a). implies (equal (length l) 0) (P l))) (P nil)))
THMhlength_map2'c,'a,'b:S. (all (l1:hlist{}('a). all (l2:hlist{}('b). implies (equal (length l1) (length l2)) (all (f:'a 'b 'c. and (equal (length (map2 f l1 l2)) (length l1)) (equal (length (map2 f l1 l2)) (length l2)))))))
THMhnull_eq_nil'a:S. (all (l:hlist{}('a). equal (null l) (equal l nil)))
THMhlength_eq'a:S (all (x:hlist{}('a). all (y:hlist{}('a). implies (equal x y) (equal (length x) (length y)))))
THMhlength_not_null'a:S. (all (l:hlist{}('a). equal (lt 0 (length l)) (not (null l))))
THMhreverse_snoc'a:S (all (x:'a. all (l:hlist{}('a). equal (reverse (snoc x l)) (cons x (reverse l)))))
THMhreverse_reverse'a:S. (all (l:hlist{}('a). equal (reverse (reverse l)) l))
THMhsnoc_axiom'b,'a:S. (all (e:'b. all (f:'b 'a hlist{}('a) 'b. exists_unique (fn1:hlist{}('a) 'b. and (equal (fn1 nil) e) (all (x:'a. all (l:hlist{}('a). equal (fn1 (snoc x l)) (f (fn1 l) x l))))))))
THMhsnoc_induct'a:S (all (P:hlist{}('a) hbool{}. implies (and (P nil) (all (l:hlist{}('a). implies (P l) (all (x:'a. P (snoc x l)))))) (all (l:hlist{}('a). P l))))
THMhsnoc_cases'a:S (all (l:hlist{}('a). or (equal l nil) (exists (l':hlist{}('a). exists (x:'a. equal l (snoc x l'))))))
THMhlength_snoc'a:S (all (x:'a. all (l:hlist{}('a). equal (length (snoc x l)) (suc (length l)))))
THMhnot_nil_snoc'a:S (all (x:'a. all (l:hlist{}('a). not (equal nil (snoc x l)))))
THMhnot_snoc_nil'a:S (all (x:'a. all (l:hlist{}('a). not (equal (snoc x l) nil))))
THMhsnoc_11'a:S (all (x:'a. all (l:hlist{}('a). all (x':'a. all (l':hlist{}('a). equal (equal (snoc x l) (snoc x' l')) (and (equal x x') (equal l l')))))))
THMhsnoc_eq_length_eq'a:S (all (x1:'a. all (l1:hlist{}('a). all (x2:'a. all (l2:hlist{}('a). implies (equal (snoc x1 l1) (snoc x2 l2)) (equal (length l1) (length l2)))))))
THMhsnoc_reverse_cons'a:S (all (x:'a. all (l:hlist{}('a). equal (snoc x l) (reverse (cons x (reverse l))))))
THMhsnoc_append'a:S (all (x:'a. all (l:hlist{}('a). equal (snoc x l) (append l (cons x nil)))))
THMhmap_snoc'a,'b:S. (all (f:'a 'b. all (x:'a. all (l:hlist{}('a). equal (map f (snoc x l)) (snoc (f x) (map f l))))))
THMhfoldr_snoc'a,'b:S. (all (f:'a 'b 'b. all (e:'b. all (x:'a. all (l:hlist{}('a). equal (foldr f e (snoc x l)) (foldr f (f x e) l))))))
THMhfoldl_snoc'b,'a:S. (all (f:'b 'a 'b. all (e:'b. all (x:'a. all (l:hlist{}('a). equal (foldl f e (snoc x l)) (f (foldl f e l) x))))))
THMhfoldr_foldl'a:S (all (f:'a 'a 'a. all (e:'a. implies (monoid f e) (all (l:hlist{}('a). equal (foldr f e l) (foldl f e l))))))
THMhlength_foldr'a:S (all (l:hlist{}('a). equal (length l) (foldr (x:'a. l':hnum{}. suc l') 0 l)))
THMhlength_foldl'a:S (all (l:hlist{}('a). equal (length l) (foldl (l':hnum{}. x:'a. suc l') 0 l)))
THMhmap_foldr'a,'b:S. (all (f:'a 'b. all (l:hlist{}('a). equal (map f l) (foldr (x:'a. l':hlist{}('b). cons (f x) l') nil l))))
THMhmap_foldl'a,'b:S. (all (f:'a 'b. all (l:hlist{}('a). equal (map f l) (foldl (l':hlist{}('b). x:'a. snoc (f x) l') nil l))))
THMhmap_o_2'c,'a,'b:S. (all (f:'b 'c. all (g:'a 'b. equal (map (o f g)) (o (map f) (map g)))))
THMhmap_map_o'b,'c,'a:S. (all (f:'b 'c. all (g:'a 'b. all (l:hlist{}('a). equal (map f (map g l)) (map (o f g) l)))))
THMhfilter_foldr'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (filter P l) (foldr (x:'a. l':hlist{}('a). cond (P x) (cons x l') l') nil l))))
THMhfilter_snoc'a:S (all (P:'a hbool{}. all (x:'a. all (l:hlist{}('a). equal (filter P (snoc x l)) (cond (P x) (snoc x (filter P l)) (filter P l))))))
THMhfilter_foldl'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (filter P l) (foldl (l':hlist{}('a). x:'a. cond (P x) (snoc x l') l') nil l))))
THMhfilter_comm'a:S (all (f1:'a hbool{}. all (f2:'a hbool{}. all (l:hlist{}('a). equal (filter f1 (filter f2 l)) (filter f2 (filter f1 l))))))
THMhfilter_idem'a:S (all (f:'a hbool{}. all (l:hlist{}('a). equal (filter f (filter f l)) (filter f l))))
THMhfilter_map'b,'a:S. (all (f1:'b hbool{}. all (f2:'a 'b. all (l:hlist{}('a). equal (filter f1 (map f2 l)) (map f2 (filter (o f1 f2) l))))))
THMhlength_seg'a:S (all (n:hnum{}. all (k:hnum{}. all (l:hlist{}('a). implies (le (add n k) (length l)) (equal (length (seg n k l)) n)))))
THMhappend_nil'a:S (and (all (l:hlist{}('a). equal (append l nil) l)) (all (l:hlist{}('a). equal (append nil l) l)))
THMhappend_snoc'a:S (all (l1:hlist{}('a). all (x:'a. all (l2:hlist{}('a). equal (append l1 (snoc x l2)) (snoc x (append l1 l2))))))
THMhreverse_append_2'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (reverse (append l1 l2)) (append (reverse l2) (reverse l1)))))
THMhappend_foldr'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (append l1 l2) (foldr cons l2 l1))))
THMhappend_foldl'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (append l1 l2) (foldl (l':hlist{}('a). x:'a. snoc x l') l1 l2))))
THMhfoldr_append'a,'b:S. (all (f:'a 'b 'b. all (e:'b. all (l1:hlist{}('a). all (l2:hlist{}('a). equal (foldr f e (append l1 l2)) (foldr f (foldr f e l2) l1))))))
THMhfoldl_append'a,'b:S. (all (f:'a 'b 'a. all (e:'a. all (l1:hlist{}('b). all (l2:hlist{}('b). equal (foldl f e (append l1 l2)) (foldl f (foldl f e l1) l2))))))
THMhcons_append'a:S (all (x:'a. all (l:hlist{}('a). equal (cons x l) (append (cons x nil) l))))
THMhassoc_append'a:S. (assoc append)
THMhmonoid_append_nil'a:S. (monoid append nil)
THMhappend_length_eq'a:S (all (l1:hlist{}('a). all (l1':hlist{}('a). implies (equal (length l1) (length l1')) (all (l2:hlist{}('a). all (l2':hlist{}('a). implies (equal (length l2) (length l2')) (equal (equal (append l1 l2) (append l1' l2')) (and (equal l1 l1') (equal l2 l2')))))))))
THMhfilter_append'a:S (all (f:'a hbool{}. all (l1:hlist{}('a). all (l2:hlist{}('a). equal (filter f (append l1 l2)) (append (filter f l1) (filter f l2))))))
THMhflat_snoc'a:S (all (x:hlist{}('a). all (l:hlist{}(hlist{}('a)). equal (flat (snoc x l)) (append (flat l) x))))
THMhflat_foldr'a:S (all (l:hlist{}(hlist{}('a)). equal (flat l) (foldr append nil l)))
THMhflat_foldl'a:S (all (l:hlist{}(hlist{}('a)). equal (flat l) (foldl append nil l)))
THMhlength_flat'a:S (all (l:hlist{}(hlist{}('a)). equal (length (flat l)) (it_sum (map length l))))
THMhreverse_foldr'a:S. (all (l:hlist{}('a). equal (reverse l) (foldr snoc nil l)))
THMhreverse_foldl'a:S (all (l:hlist{}('a). equal (reverse l) (foldl (l':hlist{}('a). x:'a. cons x l') nil l)))
THMhlength_reverse'a:S. (all (l:hlist{}('a). equal (length (reverse l)) (length l)))
THMhreverse_eq_nil'a:S (all (l:hlist{}('a). equal (equal (reverse l) nil) (equal l nil)))
THMhall_el_snoc'a:S (all (P:'a hbool{}. all (x:'a. all (l:hlist{}('a). equal (all_el P (snoc x l)) (and (all_el P l) (P x))))))
THMhall_el_conj'a:S (all (P:'a hbool{}. all (Q:'a hbool{}. all (l:hlist{}('a). equal (all_el (x:'a. and (P x) (Q x)) l) (and (all_el P l) (all_el Q l))))))
THMhall_el_map'b,'a:S. (all (P:'b hbool{}. all (f:'a 'b. all (l:hlist{}('a). equal (all_el P (map f l)) (all_el (o P f) l)))))
THMhall_el_append'a:S (all (P:'a hbool{}. all (l1:hlist{}('a). all (l2:hlist{}('a). equal (all_el P (append l1 l2)) (and (all_el P l1) (all_el P l2))))))
THMhsome_el_snoc'a:S (all (P:'a hbool{}. all (x:'a. all (l:hlist{}('a). equal (some_el P (snoc x l)) (or (P x) (some_el P l))))))
THMhnot_all_el_some_el'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (not (all_el P l)) (some_el (o not P) l))))
THMhnot_some_el_all_el'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (not (some_el P l)) (all_el (o not P) l))))
THMhis_el_char'a:S (and (all (x:'a. equal (is_el x nil) f)) (all (y:'a. all (x:'a. all (l:hlist{}('a). equal (is_el y (cons x l)) (or (equal y x) (is_el y l)))))))
THMhis_el_snoc'a:S (all (y:'a. all (x:'a. all (l:hlist{}('a). equal (is_el y (snoc x l)) (or (equal y x) (is_el y l))))))
THMhsum_snoc(all (x:hnum{}. all (l:hlist{}(hnum{}). equal (it_sum (snoc x l)) (add (it_sum l) x))))
THMhsum_foldr(all (l:hlist{}(hnum{}). equal (it_sum l) (foldr add 0 l)))
THMhsum_foldl(all (l:hlist{}(hnum{}). equal (it_sum l) (foldl add 0 l)))
THMhis_prefix_append'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (is_prefix l1 l2) (exists (l:hlist{}('a). equal l1 (append l2 l))))))
THMhis_suffix_append'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (is_suffix l1 l2) (exists (l:hlist{}('a). equal l1 (append l l2))))))
THMhis_sublist_append'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (is_sublist l1 l2) (exists (l:hlist{}('a). exists (l':hlist{}('a). equal l1 (append l (append l2 l'))))))))
THMhis_prefix_is_sublist'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). implies (is_prefix l1 l2) (is_sublist l1 l2))))
THMhis_suffix_is_sublist'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). implies (is_suffix l1 l2) (is_sublist l1 l2))))
THMhis_prefix_reverse'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (is_prefix (reverse l1) (reverse l2)) (is_suffix l1 l2))))
THMhis_suffix_reverse'a:S (all (l2:hlist{}('a). all (l1:hlist{}('a). equal (is_suffix (reverse l1) (reverse l2)) (is_prefix l1 l2))))
THMhis_sublist_reverse'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (is_sublist (reverse l1) (reverse l2)) (is_sublist l1 l2))))
THMhprefix_foldr'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (prefix P l) (foldr (x:'a. l':hlist{}('a). cond (P x) (cons x l') nil) nil l))))
THMhprefix_char'a:S (and (all (P:'a hbool{}. equal (prefix P nil) nil)) (all (P:'a hbool{}. all (x:'a. all (l:hlist{}('a). equal (prefix P (cons x l)) (cond (P x) (cons x (prefix P l)) nil))))))
THMhis_prefix_prefix'a:S (all (P:'a hbool{}. all (l:hlist{}('a). is_prefix l (prefix P l))))
THMhlength_scanl'b,'a:S. (all (f:'b 'a 'b. all (e:'b. all (l:hlist{}('a). equal (length (scanl f e l)) (suc (length l))))))
THMhlength_scanr'b,'a:S. (all (f:'a 'b 'b. all (e:'b. all (l:hlist{}('a). equal (length (scanr f e l)) (suc (length l))))))
THMhcomm_monoid_foldl'a:S (all (f:'a 'a 'a. implies (comm f) (all (e':'a. implies (monoid f e') (all (e:'a. all (l:hlist{}('a). equal (foldl f e l) (f e (foldl f e' l)))))))))
THMhcomm_monoid_foldr'a:S (all (f:'a 'a 'a. implies (comm f) (all (e':'a. implies (monoid f e') (all (e:'a. all (l:hlist{}('a). equal (foldr f e l) (f e (foldr f e' l)))))))))
THMhfcomm_foldr_append'b,'a:S. (all (g:'a 'a 'a. all (f:'b 'a 'a. implies (fcomm g f) (all (e:'a. implies (left_id g e) (all (l1:hlist{}('b). all (l2:hlist{}('b). equal (foldr f e (append l1 l2)) (g (foldr f e l1) (foldr f e l2))))))))))
THMhfcomm_foldl_append'a,'b:S. (all (f:'a 'b 'a. all (g:'a 'a 'a. implies (fcomm f g) (all (e:'a. implies (right_id g e) (all (l1:hlist{}('b). all (l2:hlist{}('b). equal (foldl f e (append l1 l2)) (g (foldl f e l1) (foldl f e l2))))))))))
THMhfoldl_single'a,'b:S. (all (f:'a 'b 'a. all (e:'a. all (x:'b. equal (foldl f e (cons x nil)) (f e x)))))
THMhfoldr_single'b,'a:S. (all (f:'a 'b 'b. all (e:'b. all (x:'a. equal (foldr f e (cons x nil)) (f x e)))))
THMhfoldr_cons_nil'a:S. (all (l:hlist{}('a). equal (foldr cons nil l) l))
THMhfoldl_snoc_nil'a:S (all (l:hlist{}('a). equal (foldl (xs:hlist{}('a). x:'a. snoc x xs) nil l) l))
THMhfoldr_foldl_reverse'b,'a:S. (all (f:'a 'b 'b. all (e:'b. all (l:hlist{}('a). equal (foldr f e l) (foldl (x:'b. y:'a. f y x) e (reverse l))))))
THMhfoldl_foldr_reverse'a,'b:S. (all (f:'a 'b 'a. all (e:'a. all (l:hlist{}('b). equal (foldl f e l) (foldr (x:'b. y:'a. f y x) e (reverse l))))))
THMhfoldr_reverse'b,'a:S. (all (f:'a 'b 'b. all (e:'b. all (l:hlist{}('a). equal (foldr f e (reverse l)) (foldl (x:'b. y:'a. f y x) e l)))))
THMhfoldl_reverse'b,'a:S. (all (f:'a 'b 'a. all (e:'a. all (l:hlist{}('b). equal (foldl f e (reverse l)) (foldr (x:'b. y:'a. f y x) e l)))))
THMhfoldr_map'b,'a:S. (all (f:'a 'a 'a. all (e:'a. all (g:'b 'a. all (l:hlist{}('b). equal (foldr f e (map g l)) (foldr (x:'b. y:'a. f (g x) y) e l))))))
THMhfoldl_map'a,'b:S. (all (f:'a 'a 'a. all (e:'a. all (g:'b 'a. all (l:hlist{}('b). equal (foldl f e (map g l)) (foldl (x:'a. y:'b. f x (g y)) e l))))))
THMhall_el_foldr'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (all_el P l) (foldr (x:'a. l':hbool{}. and (P x) l') t l))))
THMhall_el_foldl'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (all_el P l) (foldl (l':hbool{}. x:'a. and l' (P x)) t l))))
THMhsome_el_foldr'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (some_el P l) (foldr (x:'a. l':hbool{}. or (P x) l') f l))))
THMhsome_el_foldl'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (some_el P l) (foldl (l':hbool{}. x:'a. or l' (P x)) f l))))
THMhall_el_foldr_map'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (all_el P l) (foldr and t (map P l)))))
THMhall_el_foldl_map'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (all_el P l) (foldl and t (map P l)))))
THMhsome_el_foldr_map'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (some_el P l) (foldr or f (map P l)))))
THMhsome_el_foldl_map'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (some_el P l) (foldl or f (map P l)))))
THMhfoldr_filter'a:S (all (f:'a 'a 'a. all (e:'a. all (P:'a hbool{}. all (l:hlist{}('a). equal (foldr f e (filter P l)) (foldr (x:'a. y:'a. cond (P x) (f x y) y) e l))))))
THMhfoldl_filter'a:S (all (f:'a 'a 'a. all (e:'a. all (P:'a hbool{}. all (l:hlist{}('a). equal (foldl f e (filter P l)) (foldl (x:'a. y:'a. cond (P y) (f x y) x) e l))))))
THMhassoc_foldr_flat'a:S (all (f:'a 'a 'a. implies (assoc f) (all (e:'a. implies (left_id f e) (all (l:hlist{}(hlist{}('a)). equal (foldr f e (flat l)) (foldr f e (map (foldr f e) l))))))))
THMhassoc_foldl_flat'a:S (all (f:'a 'a 'a. implies (assoc f) (all (e:'a. implies (right_id f e) (all (l:hlist{}(hlist{}('a)). equal (foldl f e (flat l)) (foldl f e (map (foldl f e) l))))))))
THMhmap_flat'a,'b:S. (all (f:'a 'b. all (l:hlist{}(hlist{}('a)). equal (map f (flat l)) (flat (map (map f) l)))))
THMhfilter_flat'a:S (all (P:'a hbool{}. all (l:hlist{}(hlist{}('a)). equal (filter P (flat l)) (flat (map (filter P) l)))))
THMhsome_el_map'b,'a:S. (all (P:'b hbool{}. all (f:'a 'b. all (l:hlist{}('a). equal (some_el P (map f l)) (some_el (o P f) l)))))
THMhsome_el_append'a:S (all (P:'a hbool{}. all (l1:hlist{}('a). all (l2:hlist{}('a). equal (some_el P (append l1 l2)) (or (some_el P l1) (some_el P l2))))))
THMhsome_el_disj'a:S (all (P:'a hbool{}. all (Q:'a hbool{}. all (l:hlist{}('a). equal (some_el (x:'a. or (P x) (Q x)) l) (or (some_el P l) (some_el Q l))))))
THMhis_el_append'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). all (x:'a. equal (is_el x (append l1 l2)) (or (is_el x l1) (is_el x l2))))))
THMhis_el_foldr'a:S (all (y:'a. all (l:hlist{}('a). equal (is_el y l) (foldr (x:'a. l':hbool{}. or (equal y x) l') f l))))
THMhis_el_foldl'a:S (all (y:'a. all (l:hlist{}('a). equal (is_el y l) (foldl (l':hbool{}. x:'a. or l' (equal y x)) f l))))
THMhnull_foldr'a:S (all (l:hlist{}('a). equal (null l) (foldr (x:'a. l':hbool{}. f) t l)))
THMhnull_foldl'a:S (all (l:hlist{}('a). equal (null l) (foldl (x:hbool{}. l':'a. f) t l)))
THMhmap_reverse'a,'b:S. (all (f:'a 'b. all (l:hlist{}('a). equal (map f (reverse l)) (reverse (map f l)))))
THMhfilter_reverse'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (filter P (reverse l)) (reverse (filter P l)))))
THMhlast_char'a:S. (all (x:'a. all (l:hlist{}('a). equal (last (snoc x l)) x)))
THMhbutlast_char'a:S (all (x:'a. all (l:hlist{}('a). equal (butlast (snoc x l)) l)))
THMhseg_length_id'a:S. (all (l:hlist{}('a). equal (seg (length l) 0 l) l))
THMhseg_suc_cons'a:S (all (m:hnum{}. all (n:hnum{}. all (l:hlist{}('a). all (x:'a. equal (seg m (suc n) (cons x l)) (seg m n l))))))
THMhseg_0_snoc'a:S (all (m:hnum{}. all (l:hlist{}('a). all (x:'a. implies (le m (length l)) (equal (seg m 0 (snoc x l)) (seg m 0 l))))))
THMhbutlastn_seg'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (butlastn n l) (seg (sub (length l) n) 0 l)))))
THMhlastn_cons'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (all (x:'a. equal (lastn n (cons x l)) (lastn n l))))))
THMhlength_lastn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (length (lastn n l)) n))))
THMhlastn_length_id'a:S. (all (l:hlist{}('a). equal (lastn (length l) l) l))
THMhlastn_lastn'a:S (all (l:hlist{}('a). all (n:hnum{}. all (m:hnum{}. implies (le m (length l)) (implies (le n m) (equal (lastn n (lastn m l)) (lastn n l)))))))
THMhfirstn_length_id'a:S. (all (l:hlist{}('a). equal (firstn (length l) l) l))
THMhfirstn_snoc'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (all (x:'a. equal (firstn n (snoc x l)) (firstn n l))))))
THMhbutlastn_length_nil'a:S. (all (l:hlist{}('a). equal (butlastn (length l) l) nil))
THMhbutlastn_suc_butlast'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (butlastn (suc n) l) (butlastn n (butlast l))))))
THMhbutlastn_butlast'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (butlastn n (butlast l)) (butlast (butlastn n l))))))
THMhlength_butlastn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (length (butlastn n l)) (sub (length l) n)))))
THMhbutlastn_butlastn'a:S (all (m:hnum{}. all (n:hnum{}. all (l:hlist{}('a). implies (le (add n m) (length l)) (equal (butlastn n (butlastn m l)) (butlastn (add n m) l))))))
THMhappend_butlastn_lastn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (append (butlastn n l) (lastn n l)) l))))
THMhappend_firstn_lastn'a:S (all (m:hnum{}. all (n:hnum{}. all (l:hlist{}('a). implies (equal (add m n) (length l)) (equal (append (firstn n l) (lastn m l)) l)))))
THMhbutlastn_append2'a:S (all (n:hnum{}. all (l1:hlist{}('a). all (l2:hlist{}('a). implies (le n (length l2)) (equal (butlastn n (append l1 l2)) (append l1 (butlastn n l2)))))))
THMhbutlastn_length_append'a:S (all (l2:hlist{}('a). all (l1:hlist{}('a). equal (butlastn (length l2) (append l1 l2)) l1)))
THMhlastn_length_append'a:S (all (l2:hlist{}('a). all (l1:hlist{}('a). equal (lastn (length l2) (append l1 l2)) l2)))
THMhbutlastn_cons'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (all (x:'a. equal (butlastn n (cons x l)) (cons x (butlastn n l)))))))
THMhbutlastn_length_cons'a:S (all (l:hlist{}('a). all (x:'a. equal (butlastn (length l) (cons x l)) (cons x nil))))
THMhlast_lastn_last'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (implies (lt 0 n) (equal (last (lastn n l)) (last l))))))
THMhbutlastn_lastn_nil'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (butlastn n (lastn n l)) nil))))
THMhlastn_butlastn'a:S (all (n:hnum{}. all (m:hnum{}. all (l:hlist{}('a). implies (le (add n m) (length l)) (equal (lastn n (butlastn m l)) (butlastn m (lastn (add n m) l)))))))
THMhbutlastn_lastn'a:S (all (m:hnum{}. all (n:hnum{}. all (l:hlist{}('a). implies (and (le m n) (le n (length l))) (equal (butlastn m (lastn n l)) (lastn (sub n m) (butlastn m l)))))))
THMhlastn_1'a:S (all (l:hlist{}('a). implies (not (equal l nil)) (equal (lastn 1 l) (cons (last l) nil))))
THMhbutlastn_1'a:S (all (l:hlist{}('a). implies (not (equal l nil)) (equal (butlastn 1 l) (butlast l))))
THMhbutlastn_append1'a:S (all (l2:hlist{}('a). all (n:hnum{}. implies (le (length l2) n) (all (l1:hlist{}('a). equal (butlastn n (append l1 l2)) (butlastn (sub n (length l2)) l1))))))
THMhlastn_append2'a:S (all (n:hnum{}. all (l2:hlist{}('a). implies (le n (length l2)) (all (l1:hlist{}('a). equal (lastn n (append l1 l2)) (lastn n l2))))))
THMhlastn_append1'a:S (all (l2:hlist{}('a). all (n:hnum{}. implies (le (length l2) n) (all (l1:hlist{}('a). equal (lastn n (append l1 l2)) (append (lastn (sub n (length l2)) l1) l2))))))
THMhlastn_map'b,'a:S. (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (all (f:'a 'b. equal (lastn n (map f l)) (map f (lastn n l)))))))
THMhbutlastn_map'b,'a:S. (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (all (f:'a 'b. equal (butlastn n (map f l)) (map f (butlastn n l)))))))
THMhall_el_lastn'a:S (all (P:'a hbool{}. all (l:hlist{}('a). implies (all_el P l) (all (m:hnum{}. implies (le m (length l)) (all_el P (lastn m l)))))))
THMhall_el_butlastn'a:S (all (P:'a hbool{}. all (l:hlist{}('a). implies (all_el P l) (all (m:hnum{}. implies (le m (length l)) (all_el P (butlastn m l)))))))
THMhlength_firstn_2'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (length (firstn n l)) n))))
THMhfirstn_firstn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (n:hnum{}. implies (le n m) (equal (firstn n (firstn m l)) (firstn n l)))))))
THMhlength_butfirstn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (length (butfirstn n l)) (sub (length l) n)))))
THMhbutfirstn_length_nil'a:S. (all (l:hlist{}('a). equal (butfirstn (length l) l) nil))
THMhbutfirstn_append1'a:S (all (n:hnum{}. all (l1:hlist{}('a). implies (le n (length l1)) (all (l2:hlist{}('a). equal (butfirstn n (append l1 l2)) (append (butfirstn n l1) l2))))))
THMhbutfirstn_append2'a:S (all (l1:hlist{}('a). all (n:hnum{}. implies (le (length l1) n) (all (l2:hlist{}('a). equal (butfirstn n (append l1 l2)) (butfirstn (sub n (length l1)) l2))))))
THMhbutfirstn_butfirstn'a:S (all (n:hnum{}. all (m:hnum{}. all (l:hlist{}('a). implies (le (add n m) (length l)) (equal (butfirstn n (butfirstn m l)) (butfirstn (add n m) l))))))
THMhappend_firstn_butfirstn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (append (firstn n l) (butfirstn n l)) l))))
THMhlastn_seg'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (lastn n l) (seg n (sub (length l) n) l)))))
THMhfirstn_seg'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (firstn n l) (seg n 0 l)))))
THMhbutfirstn_seg'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (butfirstn n l) (seg (sub (length l) n) n l)))))
THMhappend_butlast_last'a:S (all (l:hlist{}('a). implies (not (equal l nil)) (equal (append (butlast l) (cons (last l) nil)) l)))
THMhbutfirstn_snoc'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (all (x:'a. equal (butfirstn n (snoc x l)) (snoc x (butfirstn n l)))))))
THMhappend_butlastn_butfirstn'a:S (all (m:hnum{}. all (n:hnum{}. all (l:hlist{}('a). implies (equal (add m n) (length l)) (equal (append (butlastn m l) (butfirstn n l)) l)))))
THMhseg_seg'a:S (all (n1:hnum{}. all (m1:hnum{}. all (n2:hnum{}. all (m2:hnum{}. all (l:hlist{}('a). implies (and (le (add n1 m1) (length l)) (le (add n2 m2) n1)) (equal (seg n2 m2 (seg n1 m1 l)) (seg n2 (add m1 m2) l))))))))
THMhseg_append1'a:S (all (n:hnum{}. all (m:hnum{}. all (l1:hlist{}('a). implies (le (add n m) (length l1)) (all (l2:hlist{}('a). equal (seg n m (append l1 l2)) (seg n m l1)))))))
THMhseg_append2'a:S (all (l1:hlist{}('a). all (m:hnum{}. all (n:hnum{}. all (l2:hlist{}('a). implies (and (le (length l1) m) (le n (length l2))) (equal (seg n m (append l1 l2)) (seg n (sub m (length l1)) l2)))))))
THMhseg_firstn_butfistn'a:S (all (n:hnum{}. all (m:hnum{}. all (l:hlist{}('a). implies (le (add n m) (length l)) (equal (seg n m l) (firstn n (butfirstn m l)))))))
THMhseg_append'a:S (all (m:hnum{}. all (l1:hlist{}('a). all (n:hnum{}. all (l2:hlist{}('a). implies (and (lt m (length l1)) (and (le (length l1) (add n m)) (le (add n m) (add (length l1) (length l2))))) (equal (seg n m (append l1 l2)) (append (seg (sub (length l1) m) m l1) (seg (sub (add n m) (length l1)) 0 l2))))))))
THMhseg_length_snoc'a:S (all (l:hlist{}('a). all (x:'a. equal (seg 1 (length l) (snoc x l)) (cons x nil))))
THMhseg_snoc'a:S (all (n:hnum{}. all (m:hnum{}. all (l:hlist{}('a). implies (le (add n m) (length l)) (all (x:'a. equal (seg n m (snoc x l)) (seg n m l)))))))
THMhell_seg'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (ell n l) (hd (seg 1 (pre (sub (length l) n)) l))))))
THMhsnoc_foldr'a:S (all (x:'a. all (l:hlist{}('a). equal (snoc x l) (foldr cons (cons x nil) l))))
THMhis_el_foldr_map'a:S (all (x:'a. all (l:hlist{}('a). equal (is_el x l) (foldr or f (map (equal x) l)))))
THMhis_el_foldl_map'a:S (all (x:'a. all (l:hlist{}('a). equal (is_el x l) (foldl or f (map (equal x) l)))))
THMhfilter_filter'a:S (all (P:'a hbool{}. all (Q:'a hbool{}. all (l:hlist{}('a). equal (filter P (filter Q l)) (filter (x:'a. and (P x) (Q x)) l)))))
THMhfcomm_foldr_flat'b,'a:S. (all (g:'a 'a 'a. all (f:'b 'a 'a. implies (fcomm g f) (all (e:'a. implies (left_id g e) (all (l:hlist{}(hlist{}('b)). equal (foldr f e (flat l)) (foldr g e (map (foldr f e) l)))))))))
THMhfcomm_foldl_flat'a,'b:S. (all (f:'a 'b 'a. all (g:'a 'a 'a. implies (fcomm f g) (all (e:'a. implies (right_id g e) (all (l:hlist{}(hlist{}('b)). equal (foldl f e (flat l)) (foldl g e (map (foldl f e) l)))))))))
THMhfoldr_map_reverse'b,'a:S. (all (f:'a 'a 'a. implies (all (a:'a. all (b:'a. all (c:'a. equal (f a (f b c)) (f b (f a c)))))) (all (e:'a. all (g:'b 'a. all (l:hlist{}('b). equal (foldr f e (map g (reverse l))) (foldr f e (map g l))))))))
THMhfoldr_filter_reverse'a:S (all (f:'a 'a 'a. implies (all (a:'a. all (b:'a. all (c:'a. equal (f a (f b c)) (f b (f a c)))))) (all (e:'a. all (P:'a hbool{}. all (l:hlist{}('a). equal (foldr f e (filter P (reverse l))) (foldr f e (filter P l))))))))
THMhcomm_assoc_foldr_reverse'a:S (all (f:'a 'a 'a. implies (comm f) (implies (assoc f) (all (e:'a. all (l:hlist{}('a). equal (foldr f e (reverse l)) (foldr f e l)))))))
THMhcomm_assoc_foldl_reverse'a:S (all (f:'a 'a 'a. implies (comm f) (implies (assoc f) (all (e:'a. all (l:hlist{}('a). equal (foldl f e (reverse l)) (foldl f e l)))))))
THMhell_last'a:S (all (l:hlist{}('a). implies (not (null l)) (equal (ell 0 l) (last l))))
THMhell_0_snoc'a:S (all (l:hlist{}('a). all (x:'a. equal (ell 0 (snoc x l)) x)))
THMhell_snoc'a:S (all (n:hnum{}. implies (lt 0 n) (all (x:'a. all (l:hlist{}('a). equal (ell n (snoc x l)) (ell (pre n) l))))))
THMhell_suc_snoc'a:S (all (n:hnum{}. all (x:'a. all (l:hlist{}('a). equal (ell (suc n) (snoc x l)) (ell n l)))))
THMhell_cons'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (all (x:'a. equal (ell n (cons x l)) (ell n l))))))
THMhell_length_cons'a:S (all (l:hlist{}('a). all (x:'a. equal (ell (length l) (cons x l)) x)))
THMhell_length_snoc'a:S (all (l:hlist{}('a). all (x:'a. equal (ell (length l) (snoc x l)) (cond (null l) x (hd l)))))
THMhell_append2'a:S (all (n:hnum{}. all (l2:hlist{}('a). implies (lt n (length l2)) (all (l1:hlist{}('a). equal (ell n (append l1 l2)) (ell n l2))))))
THMhell_append1'a:S (all (l2:hlist{}('a). all (n:hnum{}. implies (le (length l2) n) (all (l1:hlist{}('a). equal (ell n (append l1 l2)) (ell (sub n (length l2)) l1))))))
THMhell_pre_length'a:S (all (l:hlist{}('a). implies (not (equal l nil)) (equal (ell (pre (length l)) l) (hd l))))
THMhel_length_snoc'a:S (all (l:hlist{}('a). all (x:'a. equal (el (length l) (snoc x l)) x)))
THMhel_pre_length'a:S (all (l:hlist{}('a). implies (not (equal l nil)) (equal (el (pre (length l)) l) (last l))))
THMhel_snoc'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (all (x:'a. equal (el n (snoc x l)) (el n l))))))
THMhel_ell'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (el n l) (ell (pre (sub (length l) n)) l)))))
THMhel_length_append'a:S (all (l2:hlist{}('a). all (l1:hlist{}('a). implies (not (null l2)) (equal (el (length l1) (append l1 l2)) (hd l2)))))
THMhell_el'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (ell n l) (el (pre (sub (length l) n)) l)))))
THMhell_map'b,'a:S. (all (n:hnum{}. all (l:hlist{}('a). all (f:'a 'b. implies (lt n (length l)) (equal (ell n (map f l)) (f (ell n l)))))))
THMhlength_butlast'a:S (all (l:hlist{}('a). implies (not (equal l nil)) (equal (length (butlast l)) (pre (length l)))))
THMhbutfirstn_length_append'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (butfirstn (length l1) (append l1 l2)) l2)))
THMhfirstn_append1'a:S (all (n:hnum{}. all (l1:hlist{}('a). implies (le n (length l1)) (all (l2:hlist{}('a). equal (firstn n (append l1 l2)) (firstn n l1))))))
THMhfirstn_append2'a:S (all (l1:hlist{}('a). all (n:hnum{}. implies (le (length l1) n) (all (l2:hlist{}('a). equal (firstn n (append l1 l2)) (append l1 (firstn (sub n (length l1)) l2)))))))
THMhfirstn_length_append'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). equal (firstn (length l1) (append l1 l2)) l1)))
THMhreverse_flat'a:S (all (l:hlist{}(hlist{}('a)). equal (reverse (flat l)) (flat (reverse (map reverse l)))))
THMhmap_filter'a:S (all (f:'a 'a. all (P:'a hbool{}. all (l:hlist{}('a). implies (all (x:'a. equal (P (f x)) (P x))) (equal (map f (filter P l)) (filter P (map f l)))))))
THMhflat_append'a:S (all (l1:hlist{}(hlist{}('a)). all (l2:hlist{}(hlist{}('a)). equal (flat (append l1 l2)) (append (flat l1) (flat l2)))))
THMhflat_reverse'a:S (all (l:hlist{}(hlist{}('a)). equal (flat (reverse l)) (reverse (flat (map reverse l)))))
THMhflat_flat'a:S (all (l:hlist{}(hlist{}(hlist{}('a))). equal (flat (flat l)) (flat (map flat l))))
THMhall_el_reverse'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (all_el P (reverse l)) (all_el P l))))
THMhsome_el_reverse'a:S (all (P:'a hbool{}. all (l:hlist{}('a). equal (some_el P (reverse l)) (some_el P l))))
THMhall_el_seg'a:S (all (P:'a hbool{}. all (l:hlist{}('a). implies (all_el P l) (all (m:hnum{}. all (k:hnum{}. implies (le (add m k) (length l)) (all_el P (seg m k l))))))))
THMhall_el_firstn'a:S (all (P:'a hbool{}. all (l:hlist{}('a). implies (all_el P l) (all (m:hnum{}. implies (le m (length l)) (all_el P (firstn m l)))))))
THMhall_el_butfirstn'a:S (all (P:'a hbool{}. all (l:hlist{}('a). implies (all_el P l) (all (m:hnum{}. implies (le m (length l)) (all_el P (butfirstn m l)))))))
THMhsome_el_seg'a:S (all (m:hnum{}. all (k:hnum{}. all (l:hlist{}('a). implies (le (add m k) (length l)) (all (P:'a hbool{}. implies (some_el P (seg m k l)) (some_el P l)))))))
THMhsome_el_firstn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (P:'a hbool{}. implies (some_el P (firstn m l)) (some_el P l))))))
THMhsome_el_butfirstn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (P:'a hbool{}. implies (some_el P (butfirstn m l)) (some_el P l))))))
THMhsome_el_lastn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (P:'a hbool{}. implies (some_el P (lastn m l)) (some_el P l))))))
THMhsome_el_butlastn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (P:'a hbool{}. implies (some_el P (butlastn m l)) (some_el P l))))))
THMhis_el_reverse'a:S (all (x:'a. all (l:hlist{}('a). equal (is_el x (reverse l)) (is_el x l))))
THMhis_el_filter'a:S (all (P:'a hbool{}. all (x:'a. implies (P x) (all (l:hlist{}('a). equal (is_el x (filter P l)) (is_el x l))))))
THMhis_el_seg'a:S (all (n:hnum{}. all (m:hnum{}. all (l:hlist{}('a). implies (le (add n m) (length l)) (all (x:'a. implies (is_el x (seg n m l)) (is_el x l)))))))
THMhis_el_some_el'a:S (all (x:'a. all (l:hlist{}('a). equal (is_el x l) (some_el (equal x) l))))
THMhis_el_firstn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (x:'a. implies (is_el x (firstn m l)) (is_el x l))))))
THMhis_el_butfirstn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (x:'a. implies (is_el x (butfirstn m l)) (is_el x l))))))
THMhis_el_butlastn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (x:'a. implies (is_el x (butlastn m l)) (is_el x l))))))
THMhis_el_lastn'a:S (all (m:hnum{}. all (l:hlist{}('a). implies (le m (length l)) (all (x:'a. implies (is_el x (lastn m l)) (is_el x l))))))
THMhzip_snoc'a,'b:S. (all (l1:hlist{}('a). all (l2:hlist{}('b). implies (equal (length l1) (length l2)) (all (x1:'a. all (x2:'b. equal (zip (pair (snoc x1 l1) (snoc x2 l2))) (snoc (pair x1 x2) (zip (pair l1 l2)))))))))
THMhunzip_snoc'a,'b:S. (all (x:hprod{}('a; 'b). all (l:hlist{}(hprod{}('a; 'b)). equal (unzip (snoc x l)) (pair (snoc (fst x) (fst (unzip l))) (snoc (snd x) (snd (unzip l)))))))
THMhlength_zip'a,'b:S. (all (l1:hlist{}('a). all (l2:hlist{}('b). implies (equal (length l1) (length l2)) (and (equal (length (zip (pair l1 l2))) (length l1)) (equal (length (zip (pair l1 l2))) (length l2))))))
THMhlength_unzip_fst'a,'b:S. (all (l:hlist{}(hprod{}('a; 'b)). equal (length (unzip_fst l)) (length l)))
THMhlength_unzip_snd'a,'b:S. (all (l:hlist{}(hprod{}('a; 'b)). equal (length (unzip_snd l)) (length l)))
THMhzip_unzip'a,'b:S. (all (l:hlist{}(hprod{}('a; 'b)). equal (zip (unzip l)) l))
THMhunzip_zip'a,'b:S. (all (l1:hlist{}('a). all (l2:hlist{}('b). implies (equal (length l1) (length l2)) (equal (unzip (zip (pair l1 l2))) (pair l1 l2)))))
THMhsum_append(all (l1:hlist{}(hnum{}). all (l2:hlist{}(hnum{}). equal (it_sum (append l1 l2)) (add (it_sum l1) (it_sum l2)))))
THMhsum_reverse(all (l:hlist{}(hnum{}). equal (it_sum (reverse l)) (it_sum l)))
THMhsum_flat(all (l:hlist{}(hlist{}(hnum{})). equal (it_sum (flat l)) (it_sum (map it_sum l))))
THMhel_append1'a:S (all (n:hnum{}. all (l1:hlist{}('a). all (l2:hlist{}('a). implies (lt n (length l1)) (equal (el n (append l1 l2)) (el n l1))))))
THMhel_append2'a:S (all (l1:hlist{}('a). all (n:hnum{}. implies (le (length l1) n) (all (l2:hlist{}('a). equal (el n (append l1 l2)) (el (sub n (length l1)) l2))))))
THMhel_map'b,'a:S. (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (all (f:'a 'b. equal (el n (map f l)) (f (el n l)))))))
THMhel_cons'a:S (all (n:hnum{}. implies (lt 0 n) (all (x:'a. all (l:hlist{}('a). equal (el n (cons x l)) (el (pre n) l))))))
THMhel_seg'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (el n l) (hd (seg 1 n l))))))
THMhel_is_el'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (is_el (el n l) l))))
THMhtl_snoc'a:S (all (x:'a. all (l:hlist{}('a). equal (tl (snoc x l)) (cond (null l) nil (snoc x (tl l))))))
THMhel_reverse'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (el n (reverse l)) (el (pre (sub (length l) n)) l)))))
THMhel_reverse_ell'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (el n (reverse l)) (ell n l)))))
THMhell_length_append'a:S (all (l1:hlist{}('a). all (l2:hlist{}('a). implies (not (null l1)) (equal (ell (length l2) (append l1 l2)) (last l1)))))
THMhell_is_el'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (is_el (el n l) l))))
THMhell_reverse'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (ell n (reverse l)) (ell (pre (sub (length l) n)) l)))))
THMhell_reverse_el'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (lt n (length l)) (equal (ell n (reverse l)) (el n l)))))
THMhfirstn_butlastn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (firstn n l) (butlastn (sub (length l) n) l)))))
THMhbutlastn_firstn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (butlastn n l) (firstn (sub (length l) n) l)))))
THMhlastn_butfirstn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (lastn n l) (butfirstn (sub (length l) n) l)))))
THMhbutfirstn_lastn'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (butfirstn n l) (lastn (sub (length l) n) l)))))
THMhseg_lastn_butlastn'a:S (all (n:hnum{}. all (m:hnum{}. all (l:hlist{}('a). implies (le (add n m) (length l)) (equal (seg n m l) (lastn n (butlastn (sub (length l) (add n m)) l)))))))
THMhbutfirstn_reverse'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (butfirstn n (reverse l)) (reverse (butlastn n l))))))
THMhbutlastn_reverse'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (butlastn n (reverse l)) (reverse (butfirstn n l))))))
THMhlastn_reverse'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (lastn n (reverse l)) (reverse (firstn n l))))))
THMhfirstn_reverse'a:S (all (n:hnum{}. all (l:hlist{}('a). implies (le n (length l)) (equal (firstn n (reverse l)) (reverse (lastn n l))))))
THMhseg_reverse'a:S (all (n:hnum{}. all (m:hnum{}. all (l:hlist{}('a). implies (le (add n m) (length l)) (equal (seg n m (reverse l)) (reverse (seg n (sub (length l) (add n m)) l)))))))
THMhlength_genlist'a:S (all (f:hnum{} 'a. all (n:hnum{}. equal (length (genlist f n)) n)))
THMhlength_replicate'a:S (all (n:hnum{}. all (x:'a. equal (length (replicate n x)) n)))
THMhis_el_replicate'a:S (all (n:hnum{}. implies (lt 0 n) (all (x:'a. is_el x (replicate n x)))))
THMhall_el_replicate'a:S (all (x:'a. all (n:hnum{}. all_el (equal x) (replicate n x))))
THMhand_el_foldl(all (l:hlist{}(hbool{}). equal (and_el l) (foldl and t l)))
THMhand_el_foldr(all (l:hlist{}(hbool{}). equal (and_el l) (foldr and t l)))
THMhor_el_foldl(all (l:hlist{}(hbool{}). equal (or_el l) (foldl or f l)))
THMhor_el_foldr(all (l:hlist{}(hbool{}). equal (or_el l) (foldr or f l)))
THMhmap2_zip'c,'a,'b:S. (all (l1:hlist{}('a). all (l2:hlist{}('b). implies (equal (length l1) (length l2)) (all (f:'a 'b 'c. equal (map2 f l1 l2) (map (uncurry f) (zip (pair l1 l2))))))))
COMList_Nuprl_theorems--------------
THMfoldr_wd'a,'b:S. (f:'a 'b 'b. e:'b. e = e) (f:'a 'b 'b. e:'b. x:'a. l:'a List. f x foldr(f;e;l) = f x foldr(f;e;l))
THMfoldl_wd'b,'a:S. (f:'b 'a 'b. e:'b. e = e) (f:'b 'a 'b. e:'b. x:'a. l:'a List. foldl(f;f e x;l) = foldl(f;f e x;l))
THMfilter_wd'a:S (P:'a . [] = []) (P:'a . x:'a. l:'a List. if P x then x::filter(P;l) else filter(P;l) fi = if P x then x::filter(P;l) else filter(P;l) fi )
THMscanl_wd'b,'a:S. (f:'b 'a 'b. e:'b. (e::[]) = (e::[])) (f:'b 'a 'b. e:'b. x:'a. l:'a List. (e::scanl(f;f e x;l)) = (e::scanl(f;f e x;l)))
THMscanr_wd'a,'b:S. (f:'a 'b 'b. e:'b. (e::[]) = (e::[])) (f:'a 'b 'b. e:'b. x:'a. l:'a List. ((f x head(scanr(f;e;l)))::scanr(f;e;l)) = ((f x head(scanr(f;e;l)))::scanr(f;e;l)))
THMreverse_wd'a:S [] = [] (x:'a. l:'a List. rev(l) @ (x::[]) = snoc(x;rev(l)))
THMall_el_wd'a:S (P:'a . True) (P:'a . x:'a. l:'a List. P x every(P;l) = P x every(P;l))
THMsome_el_wd'a:S (P:'a . True) (P:'a . x:'a. l:'a List. (P x) some(P;l) = (P x) some(P;l))
THMis_el_def__old'a:S. x:'a. l:'a List. (x _{<eq_pred:(x:'a. y:'a. x = y)>} l) some(y:'a. x = y;l)
THMis_el_def__old1'a:S. eq:eq('a). x:'a. l:'a List. (x _{eq} l) some(y:'a. x = y;l)
THMis_el_def'a:S. eq:eq('a). x:'a. l:'a List. x _{eq} l = some(y:'a. x = y;l)
THMand_el_def(l: List. and_el(l)) = (l: List. every(x:. x;l))
THMor_el_def(l: List. or_el(l)) = (l: List. some(x:. x;l))
THMfirstn_wd'a:S (l:'a List. firstn(0;l) = []) (n:. x:'a. l:'a List. firstn(n + 1;x::l) = (x::firstn(n;l)))
THMbutfirstn_wd'a:S (l:'a List. l = l) (n:. x:'a. l:'a List. nth_tl(n + 1;x::l) = nth_tl(n;l))
THMseg_wd'a:S (k:. l:'a List. seg(0;k;l) = []) (m:. x:'a. l:'a List. seg(m + 1;0;x::l) = (x::seg(m;0;l))) (m,k:. x:'a. l:'a List. seg(m + 1;k + 1;x::l) = seg(m + 1;k;l))
THMlast_def'a:S. l:'a List. mt(l) last_el(l) = head(seg(1;||l|| - 1;l))
THMbutlast_def'a:S. l:'a List. mt(l) but_last_el(l) = seg(||l|| - 1;0;l)
THMlastn_wd'a:S (l:'a List. lastn(0;l) = []) (n:. x:'a. l:'a List. lastn(n + 1;snoc(x;l)) = snoc(x;lastn(n;l)))
THMbutlastn_wd'a:S (l:'a List. butlastn(0;l) = l) (n:. x:'a. l:'a List. butlastn(n + 1;snoc(x;l)) = butlastn(n;l))
THMis_prefix_wd__old'a:S (l:'a List. True) (x:'a. l:'a List. True) (x1:'a. l1:'a List. x2:'a. l2:'a List. x1 = x2 is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2) = x1 = x2 is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2))
THMis_prefix_wd'a:S. eq:eq('a). (l:'a List. True) (x:'a. l:'a List. True) (x1:'a. l1:'a List. x2:'a. l2:'a List. x1 = x2 is_prefix(eq;l1;l2) = x1 = x2 is_prefix(eq;l1;l2))
THMis_suffix_wd__old'a:S (l:'a List. True) (x:'a. l:'a List. is_suffix(<eq_pred:(x:'a. y:'a. x = y)>[];snoc(x;l))) (x1:'a. l1:'a List. x2:'a. l2:'a List. is_suffix(<eq_pred:(x:'a. y:'a. x = y)>snoc(x1;l1);snoc(x2;l2)) = x1 = x2 is_suffix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2))
THMis_suffix_wd'a:S. eq:eq('a). (l:'a List. True) (x:'a. l:'a List. is_suffix(eq;[];snoc(x;l))) (x1:'a. l1:'a List. x2:'a. l2:'a List. is_suffix(eq;snoc(x1;l1);snoc(x2;l2)) = x1 = x2 is_suffix(eq;l1;l2))
THMis_suffix_wd_2'a:S. eq:eq('a). (l:'a List. True) (x:'a. l:'a List. is_suffix(eq;[];snoc(x;l))) (x1:'a. l1:'a List. x2:'a. l2:'a List. is_suffix(eq;snoc(x1;l1);snoc(x2;l2)) x1 = x2 is_suffix(eq;l1;l2))
THMis_sublist_wd__old'a:S (l:'a List is_sublist(<eq_pred:(x:'a. y:'a. x = y)>l;[]) True) (x:'a. l:'a List. True) (x1:'a. l1:'a List. x2:'a. l2:'a List. (x1 = x2 is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)) is_sublist(<eq_pred:(x:'a. y:'a. x = y)>l1;x2::l2) = (x1 = x2 is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)) is_sublist(<eq_pred:(x:'a. y:'a. x = y)>l1;x2::l2))
THMis_sublist_wd'a:S. eq:eq('a). (l:'a List. is_sublist(eq;l;[]) True) (x:'a. l:'a List. True) (x1:'a. l1:'a List. x2:'a. l2:'a List. (x1 = x2 is_prefix(eq;l1;l2)) is_sublist(eq;l1;x2::l2) = (x1 = x2 is_prefix(eq;l1;l2)) is_sublist(eq;l1;x2::l2))
THMsplitp_wd'a:S (P:'a . <[], []> = <[], []>) (P:'a . x:'a. l:'a List. if P x then <[], x::l> else let <l1,l2> = splitp(P;l) in <x::l1, l2> fi = if P x then <[], x::l> else <x::(splitp(P;l).1), splitp(P;l).2> fi )
THMprefix_def'a:S. P:'a . l:'a List. prefix(P;l) = splitp((p:. p) o P;l).1
THMsuffix_def'a:S. P:'a . l:'a List. suffix(P;l) = foldl(l':'a List. x:'a. if P x then snoc(x;l') else [] fi ;[];l)
THMzip_wd'a,'b:S. [] = [] (x1:'a. l1:'a List. x2:'b. l2:'b List. (<x1, x2>::zip(l1;l2)) = (<x1, x2>::zip(l1;l2)))
THMunzip_wd'a,'b:S. <[], []> = <[], []> (x:'a 'b. l:('a 'b) List. let <x1,y> = x in <x1::(unzip(l).1), y::(unzip(l).2)> = <(x.1)::(unzip(l).1), (x.2)::(unzip(l).2)>)
THMunzip_fst_def'a,'b:S. l:('a 'b) List. unzip_fst(l) = unzip(l).1
THMunzip_snd_def'a,'b:S. l:('a 'b) List. unzip_snd(l) = unzip(l).2
THMgenlist_wd'a:S (f: 'a. rev(genlist(f;0)) = []) (f: 'a. n:. rev(genlist(f;n + 1)) = snoc(f n;rev(genlist(f;n))))
THMreplicate_wd'a:S (x:'a. replicate(0;x) = []) (n:. x:'a. replicate(n + 1;x) = (x::replicate(n;x)))
THMlist_induct_2'a:S. P:'a List . (P []) (l:'a List. (P l) (x:'a. (P (x::l)))) (l:'a List. (P l))
THMnull_def_2'a:S. x:'a. l:'a List. True
THMhd_wd_2'a:S. x:'a. l:'a List. x = x
THMtl_wd_2'a:S. x:'a. l:'a List. l = l
THMappend_wd_2'a:S (l:'a List. l = l) (l1,l2:'a List. x:'a. (x::(l1 @ l2)) = (x::(l1 @ l2)))
THMflat_wd_2'a:S [] = [] (x:'a List. l:'a List List. x @ flatten(l) = x @ flatten(l))
THMlength_wd_2'a:S. 0 = 0 (x:'a. l:'a List. ||l|| + 1 = ||l|| + 1)
THMmap_wd_2'a,'b:S. (f:'a 'b. [] = []) (f:'a 'b. x:'a. l:'a List. ((f x)::map(f;l)) = ((f x)::map(f;l)))
THMmap2_wd_2'a,'b,'c:S. (f:'a 'b 'c. [] = []) (f:'a 'b 'c. x1:'a. l1:'a List. x2:'b. l2:'b List. ((f x1 x2)::map2(f;l1;l2)) = ((f x1 x2)::map2(f;l1;l2)))
THMsum_els_wd_20 = 0 (x:. l: List. x + it_sum(l) = x + it_sum(l))
THMnull_char_2'a:S. x:'a. l:'a List. True
THMlist_cases_2'a:S. l:'a List. l = [] (l':'a List. x:'a. l = (x::l'))
THMnot_nil_cons_2'a:S. x:'a. l:'a List. ([] = (x::l))
THMnot_cons_nil_2'a:S. x:'a. l:'a List. ((x::l) = [])
THMlist_not_eq_2'a:S. l1,l2:'a List. (l1 = l2) (x1,x2:'a. ((x1::l1) = (x2::l2)))
THMnot_eq_list_2'a:S. x1,x2:'a. (x1 = x2) (l1,l2:'a List. ((x1::l1) = (x2::l2)))
THMeq_list_2'a:S. x1,x2:'a. x1 = x2 (l1,l2:'a List. l1 = l2 (x1::l1) = (x2::l2))
THMcons_wd_2'a:S. l:'a List. mt(l) ((hd l)::tl(l)) = l
THMappend_assoc_3'a:S. l1,l2,l3:'a List. l1 @ l2 @ l3 = (l1 @ l2) @ l3
THMlength_append_3'a:S. l1,l2:'a List. ||l1 @ l2|| = ||l1|| + ||l2||
THMmap_append_3'a,'b:S. f:'a 'b. l1,l2:'a List. map(f;l1 @ l2) = map(f;l1) @ map(f;l2)
THMlength_map_2'b,'a:S. l:'a List. f:'a 'b. ||map(f;l)|| = ||l||
THMlength_nil_3'a:S. l:'a List. ||l|| = 0 l = []
THMlength_cons_3'a:S. l:'a List. n:. ||l|| = n + 1 (x:'a. l':'a List. ||l'|| = n l = (x::l'))
THMlength_eq_nil_2'a:S. P:'a List . (l:'a List. ||l|| = 0 (P l)) (P [])
THMlength_map2'c,'a,'b:S. l1:'a List. l2:'b List. ||l1|| = ||l2|| (f:'a 'b 'c ||map2(f;l1;l2)|| = ||l1|| ||map2(f;l1;l2)|| = ||l2||)
THMnull_eq_nil'a:S. l:'a List. mt(l) l = []
THMlength_eq'a:S. x,y:'a List. x = y ||x|| = ||y||
THMlength_not_null'a:S. l:'a List. 0 < ||l|| mt(l)
THMreverse_snoc'a:S. x:'a. l:'a List. rev(snoc(x;l)) = (x::rev(l))
THMreverse_reverse'a:S. l:'a List. rev(rev(l)) = l
THMsnoc_axiom'b,'a:S. e:'b. f:'b 'a 'a List 'b. (fn1:'a List 'b fn1 [] = e (x:'a. l:'a List. fn1 snoc(x;l) = f (fn1 l) x l)) (fn1,y:'a List 'b. (fn1 [] = e (x:'a. l:'a List. fn1 snoc(x;l) = f (fn1 l) x l)) y [] = e (x:'a. l:'a List. y snoc(x;l) = f (y l) x l) fn1 = y)
THMsnoc_induct'a:S. P:'a List . (P []) (l:'a List. (P l) (x:'a. (P snoc(x;l)))) (l:'a List. (P l))
THMsnoc_cases'a:S. l:'a List. l = [] (l':'a List. x:'a. l = snoc(x;l'))
THMlength_snoc'a:S. x:'a. l:'a List. ||snoc(x;l)|| = ||l|| + 1
THMnot_nil_snoc'a:S. x:'a. l:'a List. ([] = snoc(x;l))
THMnot_snoc_nil'a:S. x:'a. l:'a List. (snoc(x;l) = [])
THMsnoc_11_2'a:S. x:'a. l:'a List. x':'a. l':'a List. snoc(x;l) = snoc(x';l') = x = x' l = l'
THMsnoc_11'a:S. x:'a. l:'a List. x':'a. l':'a List. snoc(x;l) = snoc(x';l') x = x' l = l'
THMsnoc_eq_length_eq'a:S. x1:'a. l1:'a List. x2:'a. l2:'a List. snoc(x1;l1) = snoc(x2;l2) ||l1|| = ||l2||
THMsnoc_reverse_cons'a:S. x:'a. l:'a List. snoc(x;l) = rev(rev(l)) @ (x::[])
THMsnoc_append'a:S. x:'a. l:'a List. snoc(x;l) = l @ (x::[])
THMmap_snoc'a,'b:S. f:'a 'b. x:'a. l:'a List. map(f;snoc(x;l)) = snoc(f x;map(f;l))
THMfoldr_snoc'a,'b:S. f:'a 'b 'b. e:'b. x:'a. l:'a List. foldr(f;e;snoc(x;l)) = foldr(f;f x e;l)
THMfoldl_snoc'b,'a:S. f:'b 'a 'b. e:'b. x:'a. l:'a List. foldl(f;e;snoc(x;l)) = f foldl(f;e;l) x
THMfoldr_foldl'a:S. f:'a 'a 'a. e:'a. monoid('a;f;e) (l:'a List. foldr(f;e;l) = foldl(f;e;l))
THMlength_foldr'a:S. l:'a List. ||l|| = foldr(x:'a. l':. l' + 1;0;l)
THMlength_foldl'a:S. l:'a List. ||l|| = foldl(l':. x:'a. l' + 1;0;l)
THMmap_foldr'a,'b:S. f:'a 'b. l:'a List. map(f;l) = foldr(x:'a. l':'b List. (f x)::l';[];l)
THMmap_foldl'a,'b:S. f:'a 'b. l:'a List. map(f;l) = foldl(l':'b List. x:'a. snoc(f x;l');[];l)
THMmap_o_2'c,'a,'b:S. f:'b 'c. g:'a 'b. (l:'a List. map(f o g;l)) = (l:'b List. map(f;l)) o (l:'a List. map(g;l))
THMmap_map_o'b,'c,'a:S. f:'b 'c. g:'a 'b. l:'a List. map(f;map(g;l)) = map(f o g;l)
THMfilter_foldr'a:S. P:'a . l:'a List. filter(P;l) = foldr(x:'a. l':'a List. if P x then x::l' else l' fi ;[];l)
THMfilter_snoc'a:S. P:'a . x:'a. l:'a List. filter(P;snoc(x;l)) = if P x then snoc(x;filter(P;l)) else filter(P;l) fi
THMfilter_foldl'a:S. P:'a . l:'a List. filter(P;l) = foldl(l':'a List. x:'a. if P x then snoc(x;l') else l' fi ;[];l)
THMfilter_comm'a:S. f1,f2:'a . l:'a List. filter(f1;filter(f2;l)) = filter(f2;filter(f1;l))
THMfilter_idem'a:S. f:'a . l:'a List. filter(f;filter(f;l)) = filter(f;l)
THMfilter_map'b,'a:S. f1:'b . f2:'a 'b. l:'a List. filter(f1;map(f2;l)) = map(f2;filter(f1 o f2;l))
THMlength_seg'a:S. n,k:. l:'a List. n + k ||l|| ||seg(n;k;l)|| = n
THMappend_nil'a:S. (l:'a List. l @ [] = l) (l:'a List. l = l)
THMappend_snoc'a:S. l1:'a List. x:'a. l2:'a List. l1 @ snoc(x;l2) = snoc(x;l1 @ l2)
THMreverse_append_2'a:S. l1,l2:'a List. rev(l2) @ rev(l1) = rev(l2) @ rev(l1)
THMappend_foldr'a:S. l1,l2:'a List. l1 @ l2 = foldr(x:'a. l:'a List. x::l;l2;l1)
THMappend_foldl'a:S. l1,l2:'a List. l1 @ l2 = foldl(l':'a List. x:'a. snoc(x;l');l1;l2)
THMfoldr_append'a,'b:S. f:'a 'b 'b. e:'b. l1,l2:'a List. foldr(f;e;l1 @ l2) = foldr(f;foldr(f;e;l2);l1)
THMfoldl_append'a,'b:S. f:'a 'b 'a. e:'a. l1,l2:'b List. foldl(f;e;l1 @ l2) = foldl(f;foldl(f;e;l1);l2)
THMcons_append'a:S. x:'a. l:'a List. (x::l) = (x::l)
THMassoc_append'a:S. assoc('a List;l1:'a List. l2:'a List. l1 @ l2)
THMmonoid_append_nil'a:S. monoid('a List;l1:'a List. l2:'a List. l1 @ l2;[])
THMappend_length_eq'a:S. l1,l1':'a List. ||l1|| = ||l1'|| (l2,l2':'a List. ||l2|| = ||l2'|| (l1 @ l2 = l1' @ l2' l1 = l1' l2 = l2'))
THMfilter_append'a:S. f:'a . l1,l2:'a List. filter(f;l1 @ l2) = filter(f;l1) @ filter(f;l2)
THMflat_snoc'a:S. x:'a List. l:'a List List. flatten(snoc(x;l)) = flatten(l) @ x
THMflat_foldr'a:S. l:'a List List. flatten(l) = foldr(l1:'a List. l2:'a List. l1 @ l2;[];l)
THMflat_foldl'a:S. l:'a List List. flatten(l) = foldl(l1:'a List. l2:'a List. l1 @ l2;[];l)
THMlength_flat'a:S. l:'a List List. ||flatten(l)|| = it_sum(map(l:'a List. ||l||;l))
THMreverse_foldr'a:S. l:'a List. rev(l) = foldr(x:'a. l:'a List. snoc(x;l);[];l)
THMreverse_foldl'a:S. l:'a List. rev(l) = foldl(l':'a List. x:'a. x::l';[];l)
THMlength_reverse'a:S. l:'a List. ||rev(l)|| = ||l||
THMreverse_eq_nil'a:S. l:'a List. rev(l) = [] l = []
THMall_el_snoc'a:S. P:'a . x:'a. l:'a List. forevery(x.(P x);snoc(x;l)) forevery(x.(P x);l) (P x)
THMall_el_conj'a:S. P,Q:'a . l:'a List. forevery(x.(P x Q x);l) forevery(x.(P x);l) forevery(x.(Q x);l)
THMall_el_map'b,'a:S. P:'b . f:'a 'b. l:'a List. forevery(x.(P x);map(f;l)) forevery(x.(P (f x));l)
THMall_el_append'a:S. P:'a . l1,l2:'a List. forevery(x.(P x);l1 @ l2) forevery(x.(P x);l1) forevery(x.(P x);l2)
THMsome_el_snoc'a:S. P:'a . x:'a. l:'a List. some(P;snoc(x;l)) (P x) some(P;l)
THMnot_all_el_some_el'a:S. P:'a . l:'a List. every(P;l) = some((p:. p) o P;l)
THMnot_some_el_all_el'a:S. P:'a . l:'a List. some(P;l) = every((p:. p) o P;l)
THMis_el_char__old'a:S (x:'a. (x _{<eq_pred:(x:'a. y:'a. x = y)>} []) False) (y,x:'a. l:'a List. (y _{<eq_pred:(x:'a. y:'a. x = y)>} (x::l)) y = x (y _{<eq_pred:(x:'a. y:'a. x = y)>} l))
THMis_el_char__old1'a:S (x:'a. (x _{<eq_pred:(x:'a. y:'a. x = y)>} [])) (y,x:'a. l:'a List. y _{<eq_pred:(x:'a. y:'a. x = y)>} (x::l) = (y = x) (y _{<eq_pred:(x:'a. y:'a. x = y)>} l))
THMis_el_char'a:S. eq:eq('a). (x:'a. (x _{eq} [])) (y,x:'a. l:'a List. y _{eq} (x::l) = (y = x) (y _{eq} l))
THMis_el_snoc__old'a:S. y,x:'a. l:'a List. (y _{<eq_pred:(x:'a. y:'a. x = y)>} snoc(x;l)) y = x (y _{<eq_pred:(x:'a. y:'a. x = y)>} l)
THMis_el_snoc__old1'a:S. y,x:'a. l:'a List. y _{<eq_pred:(x:'a. y:'a. x = y)>} snoc(x;l) = (y = x) (y _{<eq_pred:(x:'a. y:'a. x = y)>} l)
THMis_el_snoc'a:S. eq:eq('a). y,x:'a. l:'a List. y _{eq} snoc(x;l) = (y = x) (y _{eq} l)
THMsum_snocx:. l: List. it_sum(snoc(x;l)) = it_sum(l) + x
THMsum_foldrl: List. it_sum(l) = foldr(m:. n:. m + n;0;l)
THMsum_foldll: List. it_sum(l) = foldl(m:. n:. m + n;0;l)
THMis_prefix_append__old'a:S. l1,l2:'a List. is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2) (l:'a List. l1 = l2 @ l)
THMis_prefix_append'a:S. eq:eq('a). l1,l2:'a List. is_prefix(eq;l1;l2) (l:'a List. l1 = l2 @ l)
THMis_suffix_append__old'a:S. l1,l2:'a List. is_suffix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2) (l:'a List. l1 = l @ l2)
THMis_suffix_append'a:S. eq:eq('a). l1,l2:'a List. is_suffix(eq;l1;l2) (l:'a List. l1 = l @ l2)
THMis_sublist_append__old'a:S. l1,l2:'a List. is_sublist(<eq_pred:(x:'a. y:'a. x = y)>l1;l2) (l,l':'a List. l1 = l @ l2 @ l')
THMis_sublist_append'a:S. eq:eq('a). l1,l2:'a List. is_sublist(eq;l1;l2) (l,l':'a List. l1 = l @ l2 @ l')
THMis_prefix_is_sublist__old'a:S. l1,l2:'a List. is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2) is_sublist(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
THMis_prefix_is_sublist'a:S. eq:eq('a). l1,l2:'a List. is_prefix(eq;l1;l2) is_sublist(eq;l1;l2)
THMis_suffix_is_sublist__old'a:S. l1,l2:'a List. is_suffix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2) is_sublist(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
THMis_suffix_is_sublist'a:S. eq:eq('a). l1,l2:'a List. is_suffix(eq;l1;l2) is_sublist(eq;l1;l2)
THMis_prefix_reverse__old'a:S. l1,l2:'a List. is_prefix(<eq_pred:(x:'a. y:'a. x = y)>rev(l1);rev(l2)) is_suffix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
THMis_prefix_reverse__old1'a:S. eq:eq('a). l1,l2:'a List. is_prefix(eq;rev(l1);rev(l2)) is_suffix(eq;l1;l2)
THMis_prefix_reverse__old2'a:S. l1,l2:'a List. is_prefix(<eq_pred:(x:'a. y:'a. x = y)>rev(l1);rev(l2)) = is_suffix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
THMis_prefix_reverse'a:S. eq:eq('a). l1,l2:'a List. is_prefix(eq;rev(l1);rev(l2)) = is_suffix(eq;l1;l2)
THMis_suffix_reverse__old1'a:S. eq:eq('a). l2,l1:'a List. is_suffix(eq;rev(l1);rev(l2)) is_prefix(eq;l1;l2)
THMis_suffix_reverse__old'a:S. l2,l1:'a List. is_suffix(<eq_pred:(x:'a. y:'a. x = y)>rev(l1);rev(l2)) = is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
THMis_suffix_reverse'a:S. eq:eq('a). l2,l1:'a List. is_suffix(eq;rev(l1);rev(l2)) = is_prefix(eq;l1;l2)
THMis_sublist_reverse__old'a:S. l1,l2:'a List. is_sublist(<eq_pred:(x:'a. y:'a. x = y)>rev(l1);rev(l2)) = is_sublist(<eq_pred:(x:'a. y:'a. x = y)>l1;l2)
THMis_sublist_reverse'a:S. eq:eq('a). l1,l2:'a List. is_sublist(eq;rev(l1);rev(l2)) = is_sublist(eq;l1;l2)
THMprefix_foldr'a:S. P:'a . l:'a List. prefix(P;l) = foldr(x:'a. l':'a List. if P x then x::l' else [] fi ;[];l)
THMprefix_char'a:S (P:'a . prefix(P;[]) = []) (P:'a . x:'a. l:'a List. prefix(P;x::l) = if P x then x::prefix(P;l) else [] fi )
THMis_prefix_prefix__old'a:S. P:'a . l:'a List. is_prefix(<eq_pred:(x:'a. y:'a. x = y)>l;prefix(P;l))
THMis_prefix_prefix'a:S. eq:eq('a). P:'a . l:'a List. is_prefix(eq;l;prefix(P;l))
THMlength_scanl'b,'a:S. f:'b 'a 'b. e:'b. l:'a List. ||scanl(f;e;l)|| = ||l|| + 1
THMlength_scanr'b,'a:S. f:'a 'b 'b. e:'b. l:'a List. ||scanr(f;e;l)|| = ||l|| + 1
THMcomm_monoid_foldl'a:S. f:'a 'a 'a. comm('a;'a;f) (e':'a monoid('a;f;e') (e:'a. l:'a List. foldl(f;e;l) = f e foldl(f;e';l)))
THMcomm_monoid_foldr'a:S. f:'a 'a 'a. comm('a;'a;f) (e':'a monoid('a;f;e') (e:'a. l:'a List. foldr(f;e;l) = f e foldr(f;e';l)))
THMfcomm_foldr_append'b,'a:S. g:'a 'a 'a. f:'b 'a 'a. fcomm('a;'a;'b;g;f) (e:'a left_id('a;'a;g;e) (l1,l2:'b List. foldr(f;e;l1 @ l2) = g foldr(f;e;l1) foldr(f;e;l2)))
THMfcomm_foldl_append'a,'b:S. f:'a 'b 'a. g:'a 'a 'a. fcomm('a;'b;'a;f;g) (e:'a right_id('a;'a;g;e) (l1,l2:'b List. foldl(f;e;l1 @ l2) = g foldl(f;e;l1) foldl(f;e;l2)))
THMfoldl_single'a,'b:S. f:'a 'b 'a. e:'a. x:'b. f e x = f e x
THMfoldr_single'b,'a:S. f:'a 'b 'b. e:'b. x:'a. f x e = f x e
THMfoldr_cons_nil'a:S. l:'a List. foldr(x:'a. l:'a List. x::l;[];l) = l
THMfoldl_snoc_nil'a:S. l:'a List. foldl(xs:'a List. x:'a. snoc(x;xs);[];l) = l
THMfoldr_foldl_reverse'b,'a:S. f:'a 'b 'b. e:'b. l:'a List. foldr(f;e;l) = foldl(x:'b. y:'a. f y x;e;rev(l))
THMfoldl_foldr_reverse'a,'b:S. f:'a 'b 'a. e:'a. l:'b List. foldl(f;e;l) = foldr(x:'b. y:'a. f y x;e;rev(l))
THMfoldr_reverse'b,'a:S. f:'a 'b 'b. e:'b. l:'a List. foldr(f;e;rev(l)) = foldl(x:'b. y:'a. f y x;e;l)
THMfoldl_reverse'b,'a:S. f:'a 'b 'a. e:'a. l:'b List. foldl(f;e;rev(l)) = foldr(x:'b. y:'a. f y x;e;l)
THMfoldr_map'b,'a:S. f:'a 'a 'a. e:'a. g:'b 'a. l:'b List. foldr(f;e;map(g;l)) = foldr(x:'b. y:'a. f (g x) y;e;l)
THMfoldl_map'a,'b:S. f:'a 'a 'a. e:'a. g:'b 'a. l:'b List. foldl(f;e;map(g;l)) = foldl(x:'a. y:'b. f x (g y);e;l)
THMall_el_foldr'a:S. P:'a . l:'a List. every(P;l) = foldr(x:'a. l':. P x l';tt;l)
THMall_el_foldl'a:S. P:'a . l:'a List. every(P;l) = foldl(l':. x:'a. l' P x;tt;l)
THMsome_el_foldr'a:S. P:'a . l:'a List. some(P;l) = foldr(x:'a. l':. (P x) l';ff;l)
THMsome_el_foldl'a:S. P:'a . l:'a List. some(P;l) = foldl(l':. x:'a. l' (P x);ff;l)
THMall_el_foldr_map'a:S. P:'a . l:'a List. every(P;l) = foldr(p:. q:. p q;tt;map(P;l))
THMall_el_foldl_map'a:S. P:'a . l:'a List. every(P;l) = foldl(p:. q:. p q;tt;map(P;l))
THMsome_el_foldr_map'a:S. P:'a . l:'a List. some(P;l) = foldr(p:. q:. p q;ff;map(P;l))
THMsome_el_foldl_map'a:S. P:'a . l:'a List. some(P;l) = foldl(p:. q:. p q;ff;map(P;l))
THMfoldr_filter'a:S. f:'a 'a 'a. e:'a. P:'a . l:'a List. foldr(f;e;filter(P;l)) = foldr(x:'a. y:'a. if P x then f x y else y fi ;e;l)
THMfoldl_filter'a:S. f:'a 'a 'a. e:'a. P:'a . l:'a List. foldl(f;e;filter(P;l)) = foldl(x:'a. y:'a. if P y then f x y else x fi ;e;l)
THMassoc_foldr_flat'a:S. f:'a 'a 'a. assoc('a;f) (e:'a left_id('a;'a;f;e) (l:'a List List foldr(f;e;flatten(l)) = foldr(f;e;map(l:'a List. foldr(f;e;l);l))))
THMassoc_foldl_flat'a:S. f:'a 'a 'a. assoc('a;f) (e:'a right_id('a;'a;f;e) (l:'a List List foldl(f;e;flatten(l)) = foldl(f;e;map(l:'a List. foldl(f;e;l);l))))
THMmap_flat'a,'b:S. f:'a 'b. l:'a List List. map(f;flatten(l)) = flatten(map(l:'a List. map(f;l);l))
THMfilter_flat'a:S. P:'a . l:'a List List. filter(P;flatten(l)) = flatten(map(l:'a List. filter(P;l);l))
THMsome_el_map'b,'a:S. P:'b . f:'a 'b. l:'a List. some(P;map(f;l)) = some(P o f;l)
THMsome_el_append'a:S. P:'a . l1,l2:'a List. some(P;l1 @ l2) = some(P;l1) some(P;l2)
THMsome_el_disj'a:S. P,Q:'a . l:'a List. some(x:'a. (P x) (Q x);l) = some(P;l) some(Q;l)
THMis_el_append__old'a:S. l1,l2:'a List. x:'a. (x _{<eq_pred:(x:'a. y:'a. x = y)>} l1 @ l2) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l1) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l2)
THMis_el_append'a:S. eq:eq('a). l1,l2:'a List. x:'a. (x _{eq} l1 @ l2) (x _{eq} l1) (x _{eq} l2)
THMis_el_foldr__old'a:S. y:'a. l:'a List. (y _{<eq_pred:(x:'a. y:'a. x = y)>} l) foldr(x:'a. l':. (y = x) l';ff;l)
THMis_el_foldr__old1'a:S. eq:eq('a). y:'a. l:'a List. (y _{eq} l) foldr(x:'a. l':. (y = x) l';ff;l)
THMis_el_foldr'a:S. eq:eq('a). y:'a. l:'a List. y _{eq} l = foldr(x:'a. l':. (y = x) l';ff;l)
THMis_el_foldl__old'a:S. y:'a. l:'a List. (y _{<eq_pred:(x:'a. y:'a. x = y)>} l) foldl(l':. x:'a. l' (y = x);ff;l)
THMis_el_foldl__old1'a:S. eq:eq('a). y:'a. l:'a List. (y _{eq} l) foldl(l':. x:'a. l' (y = x);ff;l)
THMis_el_foldl'a:S. eq:eq('a). y:'a. l:'a List. y _{eq} l = foldl(l':. x:'a. l' (y = x);ff;l)
THMnull_foldr'a:S. l:'a List. mt(l) foldr(x:'a. l':. ff;tt;l)
THMnull_foldl'a:S. l:'a List. mt(l) foldl(x:. l':'a. ff;tt;l)
THMmap_reverse'a,'b:S. f:'a 'b. l:'a List. map(f;rev(l)) = rev(map(f;l))
THMfilter_reverse'a:S. P:'a . l:'a List. filter(P;rev(l)) = rev(filter(P;l))
THMlast_char'a:S. x:'a. l:'a List. last_el(snoc(x;l)) = x
THMbutlast_char'a:S. x:'a. l:'a List. but_last_el(snoc(x;l)) = l
THMseg_length_id'a:S. l:'a List. seg(||l||;0;l) = l
THMseg_suc_cons'a:S. m,n:. l:'a List. x:'a. seg(m;n + 1;x::l) = seg(m;n;l)
THMseg_0_snoc'a:S. m:. l:'a List. x:'a. m ||l|| seg(m;0;snoc(x;l)) = seg(m;0;l)
THMbutlastn_seg'a:S. n:. l:'a List. n ||l|| butlastn(n;l) = seg(nnsub(||l||;n);0;l)
THMlastn_cons'a:S. n:. l:'a List. n ||l|| (x:'a. lastn(n;x::l) = lastn(n;l))
THMlength_lastn'a:S. n:. l:'a List. n ||l|| ||lastn(n;l)|| = n
THMlastn_length_id'a:S. l:'a List. lastn(||l||;l) = l
THMlastn_lastn'a:S. l:'a List. n,m:. m ||l|| n m lastn(n;lastn(m;l)) = lastn(n;l)
THMfirstn_length_id'a:S. l:'a List. firstn(||l||;l) = l
THMfirstn_snoc'a:S. n:. l:'a List. n ||l|| (x:'a. firstn(n;snoc(x;l)) = firstn(n;l))
THMbutlastn_length_nil'a:S. l:'a List. butlastn(||l||;l) = []
THMbutlastn_suc_butlast'a:S. n:. l:'a List. n < ||l|| butlastn(n + 1;l) = butlastn(n;but_last_el(l))
THMbutlastn_butlast'a:S. n:. l:'a List. n < ||l|| butlastn(n;but_last_el(l)) = but_last_el(butlastn(n;l))
THMlength_butlastn'a:S. n:. l:'a List. n ||l|| ||butlastn(n;l)|| = nnsub(||l||;n)
THMbutlastn_butlastn'a:S. m,n:. l:'a List. n + m ||l|| butlastn(n;butlastn(m;l)) = butlastn(n + m;l)
THMappend_butlastn_lastn'a:S. n:. l:'a List. n ||l|| butlastn(n;l) @ lastn(n;l) = l
THMappend_firstn_lastn'a:S. m,n:. l:'a List. m + n = ||l|| firstn(n;l) @ lastn(m;l) = l
THMbutlastn_append2'a:S. n:. l1,l2:'a List. n ||l2|| butlastn(n;l1 @ l2) = l1 @ butlastn(n;l2)
THMbutlastn_length_append'a:S. l2,l1:'a List. butlastn(||l2||;l1 @ l2) = l1
THMlastn_length_append'a:S. l2,l1:'a List. lastn(||l2||;l1 @ l2) = l2
THMbutlastn_cons'a:S. n:. l:'a List. n ||l|| (x:'a. butlastn(n;x::l) = (x::butlastn(n;l)))
THMbutlastn_length_cons'a:S. l:'a List. x:'a. butlastn(||l||;x::l) = (x::[])
THMlast_lastn_last'a:S. n:. l:'a List. n ||l|| 0 < n last_el(lastn(n;l)) = last_el(l)
THMbutlastn_lastn_nil'a:S. n:. l:'a List. n ||l|| butlastn(n;lastn(n;l)) = []
THMlastn_butlastn'a:S. n,m:. l:'a List. n + m ||l|| lastn(n;butlastn(m;l)) = butlastn(m;lastn(n + m;l))
THMbutlastn_lastn'a:S. m,n:. l:'a List. m n n ||l|| butlastn(m;lastn(n;l)) = lastn(nnsub(n;m);butlastn(m;l))
THMlastn_1'a:S. l:'a List. (l = []) lastn(1;l) = (last_el(l)::[])
THMbutlastn_1'a:S. l:'a List. (l = []) butlastn(1;l) = but_last_el(l)
THMbutlastn_append1'a:S. l2:'a List. n:. ||l2|| n (l1:'a List. butlastn(n;l1 @ l2) = butlastn(nnsub(n;||l2||);l1))
THMlastn_append2'a:S. n:. l2:'a List. n ||l2|| (l1:'a List. lastn(n;l1 @ l2) = lastn(n;l2))
THMlastn_append1'a:S. l2:'a List. n:. ||l2|| n (l1:'a List. lastn(n;l1 @ l2) = lastn(nnsub(n;||l2||);l1) @ l2)
THMlastn_map'b,'a:S. n:. l:'a List. n ||l|| (f:'a 'b. lastn(n;map(f;l)) = map(f;lastn(n;l)))
THMbutlastn_map'b,'a:S. n:. l:'a List. n ||l|| (f:'a 'b. butlastn(n;map(f;l)) = map(f;butlastn(n;l)))
THMall_el_lastn'a:S. P:'a . l:'a List. every(P;l) (m:. m ||l|| every(P;lastn(m;l)))
THMall_el_butlastn'a:S. P:'a . l:'a List. every(P;l) (m:. m ||l|| every(P;butlastn(m;l)))
THMlength_firstn_2'a:S. n:. l:'a List. n ||l|| ||firstn(n;l)|| = n
THMfirstn_firstn'a:S. m:. l:'a List. m ||l|| (n:. n m firstn(n;firstn(m;l)) = firstn(n;l))
THMlength_butfirstn'a:S. n:. l:'a List. n ||l|| ||nth_tl(n;l)|| = nnsub(||l||;n)
THMbutfirstn_length_nil'a:S. l:'a List. nth_tl(||l||;l) = []
THMbutfirstn_append1'a:S. n:. l1:'a List. n ||l1|| (l2:'a List. nth_tl(n;l1 @ l2) = nth_tl(n;l1) @ l2)
THMbutfirstn_append2'a:S. l1:'a List. n:. ||l1|| n (l2:'a List. nth_tl(n;l1 @ l2) = nth_tl(nnsub(n;||l1||);l2))
THMbutfirstn_butfirstn'a:S. n,m:. l:'a List. n + m ||l|| nth_tl(n;nth_tl(m;l)) = nth_tl(n + m;l)
THMappend_firstn_butfirstn'a:S. n:. l:'a List. n ||l|| firstn(n;l) @ nth_tl(n;l) = l
THMlastn_seg'a:S. n:. l:'a List. n ||l|| lastn(n;l) = seg(n;nnsub(||l||;n);l)
THMfirstn_seg'a:S. n:. l:'a List. n ||l|| firstn(n;l) = seg(n;0;l)
THMbutfirstn_seg'a:S. n:. l:'a List. n ||l|| nth_tl(n;l) = seg(nnsub(||l||;n);n;l)
THMappend_butlast_last'a:S. l:'a List. (l = []) but_last_el(l) @ (last_el(l)::[]) = l
THMbutfirstn_snoc'a:S. n:. l:'a List. n ||l|| (x:'a. nth_tl(n;snoc(x;l)) = snoc(x;nth_tl(n;l)))
THMappend_butlastn_butfirstn'a:S. m,n:. l:'a List. m + n = ||l|| butlastn(m;l) @ nth_tl(n;l) = l
THMseg_seg'a:S. n1,m1,n2,m2:. l:'a List. n1 + m1 ||l|| n2 + m2 n1 seg(n2;m2;seg(n1;m1;l)) = seg(n2;m1 + m2;l)
THMseg_append1'a:S. n,m:. l1:'a List. n + m ||l1|| (l2:'a List. seg(n;m;l1 @ l2) = seg(n;m;l1))
THMseg_append2'a:S. l1:'a List. m,n:. l2:'a List. ||l1|| m n ||l2|| seg(n;m;l1 @ l2) = seg(n;nnsub(m;||l1||);l2)
THMseg_firstn_butfistn'a:S. n,m:. l:'a List. n + m ||l|| seg(n;m;l) = firstn(n;nth_tl(m;l))
THMseg_append'a:S. m:. l1:'a List. n:. l2:'a List. m < ||l1|| ||l1|| n + m n + m ||l1|| + ||l2|| seg(n;m;l1 @ l2) = seg(nnsub(||l1||;m);m;l1) @ seg(nnsub(n + m;||l1||);0;l2)
THMseg_length_snoc'a:S. l:'a List. x:'a. seg(1;||l||;snoc(x;l)) = (x::[])
THMseg_snoc'a:S. n,m:. l:'a List. n + m ||l|| (x:'a. seg(n;m;snoc(x;l)) = seg(n;m;l))
THMell_seg'a:S. n:. l:'a List. n < ||l|| ell(n;l) = head(seg(1;nnsub(||l||;n) - 1;l))
THMsnoc_foldr'a:S. x:'a. l:'a List. snoc(x;l) = foldr(x:'a. l:'a List. x::l;x::[];l)
THMis_el_foldr_map__old'a:S. x:'a. l:'a List. x _{<eq_pred:(x:'a. y:'a. x = y)>} l = foldr(p:. q:. p q;ff;map(y:'a. x = y;l))
THMis_el_foldr_map'a:S. eq:eq('a). x:'a. l:'a List. x _{eq} l = foldr(p:. q:. p q;ff;map(y:'a. x = y;l))
THMis_el_foldl_map'a:S. eq:eq('a). x:'a. l:'a List. x _{eq} l = foldl(p:. q:. p q;ff;map(y:'a. x = y;l))
THMfilter_filter'a:S. P,Q:'a . l:'a List. filter(P;filter(Q;l)) = filter(x:'a. P x Q x;l)
THMfcomm_foldr_flat'b,'a:S. g:'a 'a 'a. f:'b 'a 'a. fcomm('a;'a;'b;g;f) (e:'a left_id('a;'a;g;e) (l:'b List List foldr(f;e;flatten(l)) = foldr(g;e;map(l:'b List. foldr(f;e;l);l))))
THMfcomm_foldl_flat'a,'b:S. f:'a 'b 'a. g:'a 'a 'a. fcomm('a;'b;'a;f;g) (e:'a right_id('a;'a;g;e) (l:'b List List foldl(f;e;flatten(l)) = foldl(g;e;map(l:'b List. foldl(f;e;l);l))))
THMfoldr_map_reverse'b,'a:S. f:'a 'a 'a. (a,b,c:'a. f a (f b c) = f b (f a c)) (e:'a. g:'b 'a. l:'b List. foldr(f;e;map(g;rev(l))) = foldr(f;e;map(g;l)))
THMfoldr_filter_reverse'a:S. f:'a 'a 'a. (a,b,c:'a. f a (f b c) = f b (f a c)) (e:'a. P:'a . l:'a List. foldr(f;e;filter(P;rev(l))) = foldr(f;e;filter(P;l)))
THMcomm_assoc_foldr_reverse'a:S. f:'a 'a 'a. comm('a;'a;f) assoc('a;f) (e:'a. l:'a List. foldr(f;e;rev(l)) = foldr(f;e;l))
THMcomm_assoc_foldl_reverse'a:S. f:'a 'a 'a. comm('a;'a;f) assoc('a;f) (e:'a. l:'a List. foldl(f;e;rev(l)) = foldl(f;e;l))
THMell_last'a:S. l:'a List. mt(l) ell 0 l = last l
THMell_0_snoc'a:S. l:'a List. x:'a. ell(0;snoc(x;l)) = x
THMell_cons'a:S. n:. l:'a List. n < ||l|| (x:'a. ell(n;x::l) = ell(n;l))
THMell_length_cons'a:S. l:'a List. x:'a. ell(||l||;x::l) = x
THMell_length_snoc'a:S. l:'a List. x:'a. ell(||l||;snoc(x;l)) = if null(l) then x else head(l) fi
THMell_append2'a:S. n:. l2:'a List. n < ||l2|| (l1:'a List. ell(n;l1 @ l2) = ell(n;l2))
THMell_pre_length'a:S. l:'a List. (l = []) ell(||l|| - 1;l) = head(l)
THMel_length_snoc'a:S. l:'a List. x:'a. snoc(x;l)[||l||] = x
THMel_pre_length'a:S. l:'a List. (l = []) l[(||l|| - 1)] = last_el(l)
THMel_snoc'a:S. n:. l:'a List. n < ||l|| (x:'a. snoc(x;l)[n] = l[n])
THMel_ell'a:S. n:. l:'a List. n < ||l|| l[n] = ell(nnsub(||l||;n) - 1;l)
THMel_length_append'a:S. l2,l1:'a List. mt(l2) el ||l1|| (l1 @ l2) = hd l2
THMell_el'a:S. n:. l:'a List. n < ||l|| ell(n;l) = l[(nnsub(||l||;n) - 1)]
THMell_map'b,'a:S. n:. l:'a List. f:'a 'b. n < ||l|| ell(n;map(f;l)) = f ell(n;l)
THMlength_butlast'a:S. l:'a List. (l = []) ||but_last_el(l)|| = ||l|| - 1
THMbutfirstn_length_append'a:S. l1,l2:'a List. nth_tl(||l1||;l1 @ l2) = l2
THMfirstn_append1'a:S. n:. l1:'a List. n ||l1|| (l2:'a List. firstn(n;l1 @ l2) = firstn(n;l1))
THMfirstn_append2'a:S. l1:'a List. n:. ||l1|| n (l2:'a List firstn(n;l1 @ l2) = l1 @ firstn(nnsub(n;||l1||);l2))
THMfirstn_length_append'a:S. l1,l2:'a List. firstn(||l1||;l1 @ l2) = l1
THMreverse_flat'a:S. l:'a List List. rev(flatten(l)) = flatten(rev(map(l:'a List. rev(l);l)))
THMmap_filter__old'a:S. f:'a 'a. P:'a . l:'a List. (x:'a. (P (f x)) (P x)) map(f;filter(P;l)) = filter(P;map(f;l))
THMmap_filter'a:S. f:'a 'a. P:'a . l:'a List. (x:'a. P (f x) = P x) map(f;filter(P;l)) = filter(P;map(f;l))
THMflat_append'a:S. l1,l2:'a List List. flatten(l1 @ l2) = flatten(l1) @ flatten(l2)
THMflat_reverse'a:S. l:'a List List. flatten(rev(l)) = rev(flatten(map(l:'a List. rev(l);l)))
THMflat_flat'a:S. l:'a List List List. flatten(flatten(l)) = flatten(map(l:'a List List. flatten(l);l))
THMall_el_reverse'a:S. P:'a . l:'a List. every(P;rev(l)) = every(P;l)
THMsome_el_reverse__old'a:S. P:'a . l:'a List. some(P;rev(l)) some(P;l)
THMsome_el_reverse'a:S. P:'a . l:'a List. some(P;rev(l)) = some(P;l)
THMall_el_seg'a:S. P:'a . l:'a List. every(P;l) (m,k:. m + k ||l|| every(P;seg(m;k;l)))
THMall_el_firstn'a:S. P:'a . l:'a List. every(P;l) (m:. m ||l|| every(P;firstn(m;l)))
THMall_el_butfirstn'a:S. P:'a . l:'a List. every(P;l) (m:. m ||l|| every(P;nth_tl(m;l)))
THMsome_el_seg'a:S. m,k:. l:'a List. m + k ||l|| (P:'a . some(P;seg(m;k;l)) some(P;l))
THMsome_el_firstn'a:S. m:. l:'a List. m ||l|| (P:'a . some(P;firstn(m;l)) some(P;l))
THMsome_el_butfirstn'a:S. m:. l:'a List. m ||l|| (P:'a . some(P;nth_tl(m;l)) some(P;l))
THMsome_el_lastn'a:S. m:. l:'a List. m ||l|| (P:'a . some(P;lastn(m;l)) some(P;l))
THMsome_el_butlastn'a:S. m:. l:'a List. m ||l|| (P:'a . some(P;butlastn(m;l)) some(P;l))
THMis_el_reverse__old'a:S. x:'a. l:'a List. (x _{<eq_pred:(x:'a. y:'a. x = y)>} rev(l)) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l)
THMis_el_reverse__old1'a:S. eq:eq('a). x:'a. l:'a List. (x _{eq} rev(l)) (x _{eq} l)
THMis_el_reverse'a:S. eq:eq('a). x:'a. l:'a List. x _{eq} rev(l) = x _{eq} l
THMis_el_filter__old'a:S. P:'a . x:'a. (P x) (l:'a List (x _{<eq_pred:(x:'a. y:'a. x = y)>} filter(P;l)) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l))
THMis_el_filter__old1'a:S. eq:eq('a). P:'a . x:'a. (P x) (l:'a List. (x _{eq} filter(P;l)) (x _{eq} l))
THMis_el_filter'a:S. eq:eq('a). P:'a . x:'a. (P x) (l:'a List. x _{eq} filter(P;l) = x _{eq} l)
THMis_el_seg__old'a:S. n,m:. l:'a List. n + m ||l|| (x:'a (x _{<eq_pred:(x:'a. y:'a. x = y)>} seg(n;m;l)) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l))
THMis_el_seg'a:S. eq:eq('a). n,m:. l:'a List. n + m ||l|| (x:'a. (x _{eq} seg(n;m;l)) (x _{eq} l))
THMis_el_some_el__old'a:S. x:'a. l:'a List. (x _{<eq_pred:(x:'a. y:'a. x = y)>} l) some(y:'a. x = y;l)
THMis_el_some_el__old1'a:S. eq:eq('a). x:'a. l:'a List. (x _{eq} l) some(y:'a. x = y;l)
THMis_el_some_el'a:S. eq:eq('a). x:'a. l:'a List. x _{eq} l = some(y:'a. x = y;l)
THMis_el_firstn__old'a:S. m:. l:'a List. m ||l|| (x:'a (x _{<eq_pred:(x:'a. y:'a. x = y)>} firstn(m;l)) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l))
THMis_el_firstn'a:S. eq:eq('a). m:. l:'a List. m ||l|| (x:'a. (x _{eq} firstn(m;l)) (x _{eq} l))
THMis_el_butfirstn__old'a:S. m:. l:'a List. m ||l|| (x:'a (x _{<eq_pred:(x:'a. y:'a. x = y)>} nth_tl(m;l)) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l))
THMis_el_butfirstn'a:S. eq:eq('a). m:. l:'a List. m ||l|| (x:'a. (x _{eq} nth_tl(m;l)) (x _{eq} l))
THMis_el_butlastn__old'a:S. m:. l:'a List. m ||l|| (x:'a (x _{<eq_pred:(x:'a. y:'a. x = y)>} butlastn(m;l)) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l))
THMis_el_butlastn'a:S. eq:eq('a). m:. l:'a List. m ||l|| (x:'a. (x _{eq} butlastn(m;l)) (x _{eq} l))
THMis_el_lastn__old'a:S. m:. l:'a List. m ||l|| (x:'a (x _{<eq_pred:(x:'a. y:'a. x = y)>} lastn(m;l)) (x _{<eq_pred:(x:'a. y:'a. x = y)>} l))
THMis_el_lastn'a:S. eq:eq('a). m:. l:'a List. m ||l|| (x:'a. (x _{eq} lastn(m;l)) (x _{eq} l))
THMzip_snoc'a,'b:S. l1:'a List. l2:'b List. ||l1|| = ||l2|| (x1:'a. x2:'b. zip(snoc(x1;l1);snoc(x2;l2)) = snoc(<x1, x2>zip(l1;l2)))
THMunzip_snoc'a,'b:S. x:'a 'b. l:('a 'b) List. unzip(snoc(x;l)) = <snoc(x.1;unzip(l).1), snoc(x.2;unzip(l).2)>
THMlength_zip'a,'b:S. l1:'a List. l2:'b List. ||l1|| = ||l2|| ||zip(l1;l2)|| = ||l1|| ||zip(l1;l2)|| = ||l2||
THMlength_unzip_fst'a,'b:S. l:('a 'b) List. ||unzip_fst(l)|| = ||l||
THMlength_unzip_snd'a,'b:S. l:('a 'b) List. ||unzip_snd(l)|| = ||l||
THMzip_unzip'a,'b:S. l:('a 'b) List. let <l,l'> = unzip(l) in zip(l;l') = l
THMunzip_zip'a,'b:S. l1:'a List. l2:'b List. ||l1|| = ||l2|| unzip(zip(l1;l2)) = <l1, l2>
THMsum_appendl1,l2: List. it_sum(l1 @ l2) = it_sum(l1) + it_sum(l2)
THMsum_reversel: List. it_sum(rev(l)) = it_sum(l)
THMsum_flatl: List List it_sum(flatten(l)) = it_sum(map(l: List. it_sum(l);l))
THMel_append1'a:S. n:. l1,l2:'a List. n < ||l1|| (l1 @ l2)[n] = l1[n]
THMel_map'b,'a:S. n:. l:'a List. n < ||l|| (f:'a 'b. map(f;l)[n] = f l[n])
THMel_seg'a:S. n:. l:'a List. n < ||l|| l[n] = head(seg(1;n;l))
THMel_is_el__old'a:S. n:. l:'a List. n < ||l|| (l[n] _{<eq_pred:(x:'a. y:'a. x = y)>} l)
THMel_is_el'a:S. eq:eq('a). n:. l:'a List. n < ||l|| (l[n] _{eq} l)
THMtl_snoc'a:S. x:'a. l:'a List. tl(snoc(x;l)) = if null(l) then [] else snoc(x;tl(l)) fi
THMel_reverse'a:S. n:. l:'a List. n < ||l|| rev(l)[n] = l[(nnsub(||l||;n) - 1)]
THMel_reverse_ell'a:S. n:. l:'a List. n < ||l|| rev(l)[n] = ell(n;l)
THMell_length_append'a:S. l1,l2:'a List. mt(l1) ell ||l2|| (l1 @ l2) = last l1
THMell_is_el__old'a:S. n:. l:'a List. n < ||l|| (l[n] _{<eq_pred:(x:'a. y:'a. x = y)>} l)
THMell_is_el'a:S. eq:eq('a). n:. l:'a List. n < ||l|| (l[n] _{eq} l)
THMell_reverse'a:S. n:. l:'a List. n < ||l|| ell(n;rev(l)) = ell(nnsub(||l||;n) - 1;l)
THMell_reverse_el'a:S. n:. l:'a List. n < ||l|| ell(n;rev(l)) = l[n]
THMfirstn_butlastn'a:S. n:. l:'a List. n ||l|| firstn(n;l) = butlastn(nnsub(||l||;n);l)
THMbutlastn_firstn'a:S. n:. l:'a List. n ||l|| butlastn(n;l) = firstn(nnsub(||l||;n);l)
THMlastn_butfirstn'a:S. n:. l:'a List. n ||l|| lastn(n;l) = nth_tl(nnsub(||l||;n);l)
THMbutfirstn_lastn'a:S. n:. l:'a List. n ||l|| nth_tl(n;l) = lastn(nnsub(||l||;n);l)
THMseg_lastn_butlastn'a:S. n,m:. l:'a List. n + m ||l|| seg(n;m;l) = lastn(n;butlastn(nnsub(||l||;n + m);l))
THMbutfirstn_reverse'a:S. n:. l:'a List. n ||l|| nth_tl(n;rev(l)) = rev(butlastn(n;l))
THMbutlastn_reverse'a:S. n:. l:'a List. n ||l|| butlastn(n;rev(l)) = rev(nth_tl(n;l))
THMlastn_reverse'a:S. n:. l:'a List. n ||l|| lastn(n;rev(l)) = rev(firstn(n;l))
THMfirstn_reverse'a:S. n:. l:'a List. n ||l|| firstn(n;rev(l)) = rev(lastn(n;l))
THMseg_reverse'a:S. n,m:. l:'a List. n + m ||l|| seg(n;m;rev(l)) = rev(seg(n;nnsub(||l||;n + m);l))
THMlength_genlist'a:S. f: 'a. n:. ||rev(genlist(f;n))|| = n
THMlength_replicate'a:S. n:. x:'a. ||replicate(n;x)|| = n
THMis_el_replicate__old'a:S. n:. 0 < n (x:'a. (x _{<eq_pred:(x:'a. y:'a. x = y)>} replicate(n;x)))
THMis_el_replicate__old1'a:S. n:. 0 < n (x:'a. (x _{<eq_pred:(x:'a. y:'a. x = y)>} replicate(n;x)))
THMis_el_replicate'a:S. eq:eq('a). n:. 0 < n (x:'a. (x _{eq} replicate(n;x)))
THMall_el_replicate'a:S. x:'a. n:. every(y:'a. x = y;replicate(n;x))
THMand_el_foldll: List. and_el(l) = foldl(p:. q:. p q;tt;l)
THMand_el_foldr__oldl: List. and_el(l) foldr(p:. q:. p q;tt;l)
THMand_el_foldrl: List. and_el(l) = foldr(p:. q:. p q;tt;l)
THMor_el_foldl__oldl: List. or_el(l) foldl(p:. q:. p q;ff;l)
THMor_el_foldll: List. or_el(l) = foldl(p:. q:. p q;ff;l)
THMor_el_foldr__oldl: List. or_el(l) foldr(p:. q:. p q;ff;l)
THMor_el_foldrl: List. or_el(l) = foldr(p:. q:. p q;ff;l)
THMmap2_zip'c,'a,'b:S. l1:'a List. l2:'b List. ||l1|| = ||l2|| (f:'a 'b 'c map2(f;l1;l2) = map(p:'a 'b. f p.1 p.2;zip(l1;l2)))
THMell_wd'a:S (l:'a List. 0 < ||l|| ell(0;l) = last_el(l)) (n:. l:'a List. n + 1 < ||l|| ell(n + 1;l) = ell(n;but_last_el(l)))
THMel_wd_2'a:S (l:'a List. 0 < ||l|| l[0] = head(l)) (n:. l:'a List. n + 1 < ||l|| l[(n + 1)] = tl(l)[n])
THMell_snoc'a:S. n:. x:'a. l:'a List. 0 < n n - 1 < ||l|| ell(n;snoc(x;l)) = ell(n - 1;l)
THMell_suc_snoc'a:S. n:. x:'a. l:'a List. n < ||l|| ell(n + 1;snoc(x;l)) = ell(n;l)
THMell_append1'a:S. l2:'a List. n:. ||l2|| n n < ||l2|| (l1:'a List. ell(n;l1 @ l2) = ell(nnsub(n;||l2||);l1))
THMel_append2'a:S. l1:'a List. n:. ||l1|| n (l2:'a List n < ||l1|| + ||l2|| (l1 @ l2)[n] = l2[nnsub(n;||l1||)])
THMel_cons'a:S. n:. 0 < n (x:'a. l:'a List. n ||l|| (x::l)[n] = l[(n - 1)])
COMList_additional_theorems--------------
MLcancel_assert_of_every_simpdelete_simp (OLD_id_to_simp_table_lookup' `assert_of_every`) ;;
MLreplaced_hol_type_inf_hackadd_get_type_top_level_hook `hol_type_inf_hack` (\T. hol_to_nuprl T) ; ;
MLlift_assert_simpsetmap (add_to_simpset `lift_assert` o rev_lemma_to_simp) ``bequal_bools assert_of_bnot assert_of_band assert_of_bor assert_of_bimplies assert_of_every`` ;;
THMnil_if_mtA:. l:A List. mt(l) l = []
THMmap_o_3'c,'a,'b:S. f:'b 'c. g:'a 'b. l:'a List. map(f o g;l) = map(f;map(g;l))
THMall_el_snoc_2'a:S. P:'a . x:'a. l:'a List. every(P;snoc(x;l)) every(P;l) (P x)
THMall_el_conj_2'a:S. l:'a List. P,Q:'a . every(x:. P[x] Q[x];l) = every(x:. P[x];l) every(x:. Q[x];l)
THMall_el_map_2'b,'a:S. P:'b . f:'a 'b. l:'a List. every(P;map(f;l)) = every(P o f;l)
THMall_el_append_2'a:S. P:'a . l1,l2:'a List. every(P;l1 @ l2) = every(P;l1) every(P;l2)
THMsome_el_snoc_2'a:S. P:'a . x:'a. l:'a List. some(P;snoc(x;l)) = (P x) some(P;l)
THMsome_el_disj_2'a:S. P,Q:'a . l:'a List. some(x:'a. P[x] Q[x];l) = some(x:'a. P[x];l) some(x:'a. Q[x];l)
THMlength_unzip_fst_2'a,'b:S. l:('a 'b) List. ||unzip(l).1|| = ||l||
THMlength_unzip_snd_2'a,'b:S. l:('a 'b) List. ||unzip(l).2|| = ||l||
THMzip_unzip_2'a,'b:S. l:('a 'b) List. zip(unzip(l).1;unzip(l).2) = l
MLList_simpsetsimpset_adds `List` ( [bogus_simp `assert_of_every` ] @ map (\x,y. lemma_clause_simp x y) [`reverse_wd`, 2; `butfirstn_wd`, 2; `append_nil`, 1] @ appending_results lemma_simps ``every_conj_2 every_conj map_append length_map all_el_append_2 all_el_map_2 some_el_snoc_2 not_all_el_some_el not_some_el_all_el is_el_char is_el_snoc sum_snoc is_prefix_is_sublist is_suffix_is_sublist is_prefix_reverse is_suffix_reverse is_sublist_reverse prefix_char is_prefix_prefix length_scanl length_scanr firstn_wd seg_wd lastn_wd butlastn_wd genlist_wd replicate_wd length_map2 %null_eq_nil% length_not_null reverse_snoc reverse_reverse length_snoc not_nil_snoc not_snoc_nil snoc_11 map_snoc foldr_snoc foldl_snoc foldr_foldl map_o_3 filter_snoc filter_idem filter_map length_seg append_snoc foldr_append foldl_append filter_append flat_snoc comm_monoid_foldl comm_monoid_foldr fcomm_foldr_append fcomm_foldl_append foldr_cons_nil foldl_snoc_nil foldl_reverse foldr_reverse foldr_map foldl_map foldr_filter foldl_filter some_el_map some_el_append some_el_disj_2 map_reverse filter_reverse last_char butlast_char seg_length_id seg_suc_cons seg_0_snoc lastn_cons length_lastn lastn_length_id lastn_lastn firstn_length_id firstn_snoc butlastn_length_nil butlastn_suc_butlast butlastn_butlast length_butlastn append_butlastn_lastn append_firstn_lastn butlastn_append2 butlastn_length_append lastn_length_append butlastn_cons butlastn_length_cons last_lastn_last butlastn_lastn_nil lastn_1 butlastn_1 butlastn_append1 lastn_append2 lastn_append1 lastn_map butlastn_map all_el_lastn all_el_butlastn length_firstn_2 firstn_firstn length_butfirstn butfirstn_length_nil butfirstn_append1 butfirstn_append2 butfirstn_butfirstn append_firstn_butfirstn append_butlast_last butfirstn_snoc append_butlastn_butfirstn seg_seg seg_append1 seg_append seg_length_snoc seg_snoc filter_filter foldr_map_reverse foldr_filter_reverse comm_assoc_foldr_reverse comm_assoc_foldl_reverse ell_last ell_0_snoc ell_cons ell_length_co ns ell_length_snoc ell_append2 ell_pre_length el_length_snoc el_pre_length el_snoc el_length_append ell_map length_butlast butfirstn_length_append firstn_append1 firstn_append2 firstn_length_append map_filter is_el_filter is_el_seg is_el_firstn is_el_butfirstn is_el_butlastn is_el_lastn zip_snoc unzip_snoc length_zip length_unzip_fst length_unzip_snd length_unzip_fst_2 length_unzip_snd_2 zip_unzip_2 unzip_zip sum_append sum_reverse sum_flat el_append1 el_map el_is_el tl_snoc ell_length_append ell_is_el ell_reverse_el length_genlist length_replicate is_el_replicate all_el_replicate ell_wd el_wd_2 ell_snoc ell_suc_snoc ell_append1 ell_append2 el_cons`` @ appending_results rev_lemma_simps ``butlastn_butlastn lastn_butlastn butlastn_lastn`` ) ;; % Future consideration: is_prefix_append is_suffix_append is_sublist_append % true ;;
MLList_add_to_unfold_simpmap (add_to_simpset `unfold` o C lemma_to_cond_simp [DefaultSimpCondit ion]) ``nil_if_mt cons_wd_2`` ;;
MLcopy_simps_from_OLD_tablecopy_simps_from_OLD_table() ;;
MLHOL_standard_lib_simpssimpset_add `HOL_standard_lib_simps` (rec_simp [seg(x;y;[]); seg(0;x;y::z)]) ;; simpset_add `HOL_standard_lib_simps` (pattern_unfold_op_simp `but_last_el_nil` `but_last_el` [but_last_el([])]) ;; map (map (simpset_add `HOL_standard_lib_simps`) o get_simpset) ``HOL_arith list pair sum combin bool min nlogic List`` ;; %[Other simpsets: lift_assert: lift assert up over boolean connectives unfold: rewrite object of pair type to explicit pair, non-empty list to explicit cons, etc. Use Simpset1! nat_to_int: rewrite nat equalities to int equalities hol_to_nuprl: rewrite HOL logic to Nuprl logic (non-constructive) not (bnot): push (bnot) not down through connectives bequal: equal bools to iff asserts ext: reduce equalities of lambdas to quantified equalities ]% true;;
THMlength_induction'a:S. P:'a List . (l:'a List. (q:'a List. ||q|| < ||l|| P[q]) P[l]) {l:'a List. P[l]}
THMsnoc_cases_2'a:S. l:'a List. mt(l) (x:'a. q:'a List. l = snoc(x;q))
THMsnoc_induction'a:S. P:'a List . P[[]] (x:'a. l:'a List. P[l] P[snoc(x;l)]) (l:'a List. P[l])
MLmt_EqCDupdate_EqCD_additions `mt` (\p. let (),a,b = dest_equal (concl p) in if a=mt([]) & b=mt([]) then DCSSome [0] p else failwith `mt_EqCD_addition` ) ;;

the other theories