| COM | List_ancestors | operator |
| ML | List_load_ref | load_hthy "List" ;; |
| COM | List_Nuprl_defs | -------------- |
| THM | iff_asserts_iff_eq_bools | p,q: . ( p   q)   p = q |
| ML | hol_type_inf_hack | add_get_type_top_level_hook `hol_type_inf_hack` (\T. hn T) ;; |
| ML | reduce_list_ind | add_simp (`reduce_list_ind`, `list_ind`, (\e t. true), RedexC) ;; |
| DISP | snoc_df | snoc(<x:x:*><l:l:*>)== snoc(<x><l>) |
| ML | snoc_ml | snoc(x;l)==r if null(l) then x::[] else head(l)::snoc(x;tl(l)) fi |
| ML | snoc_simp | add_rec_simp [ snoc(x;[]) ; snoc(x;y::l) ] ;; |
| THM | snoc_wf | 'a:S. x:'a. l:'a List. snoc(x;l) 'a List |
| DISP | foldr_df | foldr(<f:f:*><e:e:*><l:l:*>)== foldr(<f><e><l>) |
| ML | foldr_ml | foldr(f;e;l)==r if null(l) then e else f head(l) foldr(f;e;tl(l)) fi |
| ML | foldr_simp | add_rec_simp [ foldr(f;e;[]) ; foldr(f;e;x::l) ] ;; |
| THM | foldr_wf | 'a,'b:S. f:'a  'b  'b. e:'b. l:'a List. foldr(f;e;l) 'b |
| DISP | foldl_df | foldl(<f:f:*><e:e:*><l:l:*>)== foldl(<f><e><l>) |
| ML | foldl_ml | foldl(f;e;l)==r if null(l) then e else foldl(f;f e head(l);tl(l)) fi |
| ML | foldl_simp | add_rec_simp [ foldl(f;e;[]) ; foldl(f;e;x::l) ] ;; |
| THM | foldl_wf | 'a,'b:S. f:'b  'a  'b. e:'b. l:'a List. foldl(f;e;l) 'b |
| DISP | filter_df | filter(<P:P:*><l:l:*>)== filter(<P><l>) |
| ML | filter_ml | filter(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 |
| ML | filter_simp | add_rec_simp [ filter(P;[]) ; filter(P;x::l) ] ;; |
| THM | filter_wf | 'a:S. P:'a  . l:'a List. filter(P;l) 'a List |
| DISP | scanl_df | scanl(<f:f:*><e:e:*><l:l:*>)== scanl(<f><e><l>) |
| ML | scanl_ml | scanl(f;e;l)
==r if null(l) then e::[] else e::scanl(f;f e head(l);tl(l)) fi |
| ML | scanl_simp | add_rec_simp [ scanl(f;e;[]) ; scanl(f;e;x::l) ] ;; |
| THM | scanl_wf | 'a,'b:S. f:'b  'a  'b. e:'b. l:'a List.
scanl(f;e;l) 'b List |
| DISP | scanr_df | scanr(<f:f:*><e:e:*><l:l:*>)== scanr(<f><e><l>) |
| ML | scanr_ml | scanr(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 |
| ML | scanr_simp | add_rec_simp [ scanr(f;e;[]) ; scanr(f;e;x::l) ] ;; |
| THM | scanr_wf | 'a,'b:S. f:'a  'b  'b. e:'b. l:'a List.
scanr(f;e;l) 'b List |
| ML | reverse_simp | add_rec_simp [ rev([]) ; rev(x::l) ] ;; |
| DISP | some_df | some(<P:P:*><l:l:*>)== some(<P><l>) |
| ML | some_ml | some(P;l)==r if null(l) then ff else (P head(l))  some(P;tl(l)) fi |
| ML | some_simp | add_rec_simp [ some(P;[]) ; some(P;x::l) ] ;; |
| THM | some_wf | 'a:S. P:'a  . l:'a List. some(P;l)  |
| DISP | is_el_df | Parens ::Prec(atomrel)::
{->0}<t:term>{<-}{\\? } _{<eq:eq_pred>} {->0}<l:list>{<-}
== <t> _{<eq>} <l> |
| ABS | is_el | x _{f} l == some(f x;l) |
| THM | is_el_wf | 'a:S. f:eq('a). x:'a. l:'a List. (x _{f} l)  |
| DISP | and_el_df | and_el(<l:l:*>)== and_el(<l>) |
| ABS | and_el | and_el(l) == every(Id;l) |
| THM | and_el_wf | l: List. and_el(l)  |
| ML | and_el_ml | add_matching_simp [ and_el([]) ; and_el(x::l) ]
(UnfoldTopAbC ANDTHENC Simp1C ANDTHENC FoldTopC `and_el`)
;; |
| DISP | or_el_df | or_el(<l:l:*>)== or_el(<l>) |
| ABS | or_el | or_el(l) == some(Id;l) |
| THM | or_el_wf | l: List. or_el(l)  |
| ML | or_el_ml | add_matching_simp [ or_el([]) ; or_el(x::l) ]
(UnfoldTopAbC ANDTHENC Simp1C ANDTHENC FoldTopC `or_el`)
;; |
| DISP | seg_df | seg(<m:m:*><n:n:*><l:l:*>)== seg(<m><n><l>) |
| ML | seg_ml | seg(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 |
| THM | seg_wf | 'a:S. m,n: . l:'a List. seg(m;n;l) 'a List |
| DISP | last_el_df | last_el(<l:l:*>)== last_el(<l>) |
| ABS | last_el | last_el(l) == head(seg(1;pre(||l||);l)) |
| THM | last_el_wf | 'a:S. l:'a List. mt(l)  last_el(l) 'a |
| DISP | but_last_el_df | but_last_el(<l:l:*>)== but_last_el(<l>) |
| ABS | but_last_el | but_last_el(l) == seg(pre(||l||);0;l) |
| THM | but_last_el_wf | 'a:S. l:'a List. but_last_el(l) 'a List |
| DISP | butlastn_df | butlastn(<n:n:*><l:l:*>)== butlastn(<n><l>) |
| ABS | butlastn | butlastn(n;l) == rev(nth_tl(n;rev(l))) |
| THM | butlastn_wf | 'a:S. n: . l:'a List. butlastn(n;l) 'a List |
| DISP | lastn_df | lastn(<n:n:*><l:l:*>)== lastn(<n><l>) |
| THM | not_mt_if_pos_length | 'a: . l:'a List. 0 < ||l||  ( mt(l)   True) |
| ML | not_mt_if_pos_length_lsimp | add_cond_lemma_simp `not_mt_if_pos_length` [Trivial] ;; |
| ABS | lastn | lastn(n;l) == rev(firstn(n;rev(l))) |
| DISP | ell_df | ell(<n:n:*><l:l:*>)== ell(<n><l>) |
| ML | ell_ml | ell(n;l)
==r if (n = 0) then last_el(l) else ell(n - 1;but_last_el(l)) fi |
| THM | ell_wf | 'a:S. n: . l:'a List. n < ||l||  ell(n;l) 'a |
| THM | lastn_wf | 'a:S. n: . l:'a List. lastn(n;l) 'a List |
| DISP | is_prefix_df | is_prefix(<f:f:*><l1:l1:*><l2:l2:*>)== is_prefix(<f><l1><l2>) |
| ML | is_prefix_ml | is_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 |
| ML | is_prefix_simp | add_rec_simp [ is_prefix(f;l;[]) ; is_prefix(f;x::y;x'::y') ;
is_prefix(f;[];x::y) ; is_prefix(f;x::y;[]) ] ;; |
| THM | is_prefix_wf | 'a:S. f:eq('a). l1,l2:'a List. is_prefix(f;l1;l2)  |
| DISP | is_suffix_df | is_suffix(<f:f:*><l1:l1:*><l2:l2:*>)== is_suffix(<f><l1><l2>) |
| ABS | is_suffix | is_suffix(f;l1;l2) == is_prefix(f;rev(l1);rev(l2)) |
| ML | is_suffix_simp | add_matching_simp [ is_suffix(f;l;[]) ; is_suffix(f;x::y;x'::y') ;
is_suffix(f;[];x::y) ; is_suffix(f;x::y;[]) ]
UnfoldTopAbC ;; |
| THM | is_suffix_wf | 'a:S. f:eq('a). l1,l2:'a List. is_suffix(f;l1;l2)  |
| DISP | is_sublist_df | is_sublist(<f:f:*><l1:l1:*><l2:l2:*>)== is_sublist(<f><l1><l2>) |
| ML | is_sublist_ml | is_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 |
| ML | is_sublist_simp | add_rec_simp [ is_sublist(f;[];[]) ; is_sublist(f;x::y;x'::y') ;
is_sublist(f;[];x::y) ; is_sublist(f;x::y;[]) ] ;; |
| THM | is_sublist_wf | 'a:S. f:eq('a). l1,l2:'a List. is_sublist(f;l1;l2)  |
| DISP | splitp_df | splitp(<P:P:*><l:l:*>)== splitp(<P><l>) |
| ML | splitp_ml | splitp(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 |
| ML | splitp_simp | add_rec_simp [ splitp(P;[]) ; splitp(P;x::l) ] ;; |
| THM | splitp_wf | 'a:S. P:'a  . l:'a List. splitp(P;l) 'a List 'a List |
| DISP | prefix_df | prefix(<P:P:*><l:l:*>)== prefix(<P><l>) |
| ABS | prefix | prefix(P;l) == splitp(( b: .  b) o P;l).1 |
| THM | prefix_wf | 'a:S. P:'a  . l:'a List. prefix(P;l) 'a List |
| DISP | suffix_df | suffix(<P:P:*><l:l:*>)== suffix(<P><l>) |
| ABS | suffix | suffix(P;l) == foldl( l',x.if P x then snoc(x;l') else [] fi ;[];l) |
| THM | suffix_wf | 'a:S. P:'a  . l:'a List. suffix(P;l) 'a List |
| DISP | zip_df | zip(<l:l:*><l':l':*>)== zip(<l><l'>) |
| ML | zip_ml | zip(l;l')
==r if null(l)
then []
else if null(l')
then []
else <head(l), head(l')>::zip(tl(l);tl(l'))
fi
fi |
| ML | zip_simp | add_rec_simp [ zip([];l') ; zip(x:::l;[]) ; zip(x:::l;x'::l') ] ;; |
| THM | zip_wf | 'a,'b:S. l:'a List. l':'b List. zip(l;l') ('a 'b) List |
| DISP | unzip_df | unzip(<l:l:*>)== unzip(<l>) |
| ML | unzip_ml | unzip(l)
==r if null(l)
then <[], []>
else let <x,y> = head(l)
in
<x::(unzip(tl(l)).1), y::(unzip(tl(l)).2)>
fi |
| ML | unzip_simp | add_rec_simp [ unzip([]) ; unzip(<x, y>::l) ] ;; |
| THM | unzip_wf | 'a,'b:S. l:('a 'b) List. unzip(l) 'a List 'b List |
| DISP | unzip_fst_df | unzip_fst(<l:l:*>)== unzip_fst(<l>) |
| ABS | unzip_fst | unzip_fst(l) == unzip(l).1 |
| THM | unzip_fst_wf | 'a,'b:S. l:('a 'b) List. unzip_fst(l) 'a List |
| DISP | unzip_snd_df | unzip_snd(<l:l:*>)== unzip_snd(<l>) |
| ABS | unzip_snd | unzip_snd(l) == unzip(l).2 |
| THM | unzip_snd_wf | 'a,'b:S. l:('a 'b) List. unzip_snd(l) 'b List |
| DISP | genlist_df | genlist(<f:f:*><n:n:*>)== genlist(<f><n>) |
| ML | genlist_ml | genlist(f;n)
==r if (n = 0) then [] else (f (n - 1))::genlist(f;n - 1) fi |
| THM | genlist_wf | 'a:S. f:  'a. n: . genlist(f;n) 'a List |
| DISP | replicate_df | replicate(<n:n:*><x:x:*>)== replicate(<n><x>) |
| ML | replicate_ml | replicate(n;x)==r if (n = 0) then [] else x::replicate(n - 1;x) fi |
| THM | replicate_wf | 'a:S. n: . x:'a. replicate(n;x) 'a List |
| COM | List_Nuprl_aux | -------------- |
| COM | List_HOL_type_defs | -------------- |
| COM | List_HOL_const_defs | -------------- |
| DISP | hsnoc_df | snoc== snoc |
| ABS | hsnoc | snoc == x:'a. l:'a List. snoc(x;l) |
| ML | hsnoc_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hsnoc");; add_info `dire
ct_new_hdef` `hsnoc`;; |
| DISP | hfoldr_df | foldr== foldr |
| ABS | hfoldr | foldr == f:'a  'b  'b. e:'b. l:'a List. foldr(f;e;l) |
| ML | hfoldr_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hfoldr");; add_info `dir
ect_new_hdef` `hfoldr`;; |
| DISP | hfoldl_df | foldl== foldl |
| ABS | hfoldl | foldl == f:'b  'a  'b. e:'b. l:'a List. foldl(f;e;l) |
| ML | hfoldl_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hfoldl");; add_info `dir
ect_new_hdef` `hfoldl`;; |
| ML | hfoldl_simp | add_rec_simp [ foldl(f;e;[]) ; foldl(f;e;x::l) ] ;; |
| DISP | hfilter_df | filter== filter |
| ABS | hfilter | filter == P:'a  . l:'a List. filter(P;l) |
| ML | hfilter_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hfilter");; add_info `di
rect_new_hdef` `hfilter`;; |
| DISP | hscanl_df | scanl== scanl |
| ABS | hscanl | scanl == f:'b  'a  'b. e:'b. l:'a List. scanl(f;e;l) |
| ML | hscanl_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hscanl");; add_info `dir
ect_new_hdef` `hscanl`;; |
| DISP | hscanr_df | scanr== scanr |
| ABS | hscanr | scanr == f:'a  'b  'b. e:'b. l:'a List. scanr(f;e;l) |
| ML | hscanr_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hscanr");; add_info `dir
ect_new_hdef` `hscanr`;; |
| DISP | hreverse_df | reverse== reverse |
| ABS | hreverse | reverse == l:'a List. rev(l) |
| ML | hreverse_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hreverse");; add_info `d
irect_old_hdef` `hreverse`;; |
| DISP | hall_el_df | all_el== all_el |
| ABS | hall_el | all_el == P:'a  . l:'a List. every(P;l) |
| ML | hall_el_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hall_el");; add_info `di
rect_old_hdef` `hall_el`;; |
| DISP | hsome_el_df | some_el== some_el |
| ABS | hsome_el | some_el == P:'a  . l:'a List. some(P;l) |
| ML | hsome_el_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hsome_el");; add_info `d
irect_new_hdef` `hsome_el`;; |
| DISP | his_el_df | is_el== is_el |
| ABS | his_el | is_el == x:'a. l:'a List. x _{<eq_pred:( x:'a. y:'a. x = y)>} l |
| ML | his_el_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "his_el");; add_info `dir
ect_new_hdef` `his_el`;; |
| DISP | hand_el_df | and_el== and_el |
| ABS | hand_el | and_el == l: List. and_el(l) |
| ML | hand_el_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hand_el");; add_info `di
rect_new_hdef` `hand_el`;; |
| DISP | hor_el_df | or_el== or_el |
| ABS | hor_el | or_el == l: List. or_el(l) |
| ML | hor_el_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hor_el");; add_info `dir
ect_new_hdef` `hor_el`;; |
| DISP | hfirstn_df | firstn== firstn |
| ABS | hfirstn | firstn == n: . l:'a List. firstn(n;l) |
| ML | hfirstn_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hfirstn");; add_info `di
rect_old_hdef` `hfirstn`;; |
| DISP | hbutfirstn_df | butfirstn== butfirstn |
| ABS | hbutfirstn | butfirstn == n: . l:'a List. nth_tl(n;l) |
| ML | hbutfirstn_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hbutfirstn");; add_info
`direct_old_hdef` `hbutfirstn`;; |
| DISP | hseg_df | seg== seg |
| ABS | hseg | seg == m: . n: . l:'a List. seg(m;n;l) |
| ML | hseg_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hseg");; add_info `direc
t_new_hdef` `hseg`;; |
| DISP | hlast_df | last== last |
| ABS | hlast | last == l:'a List. if null(l) then arb('a) else last_el(l) fi |
| THM | hlast_nuprl | 'a:S. l:'a List. mt(l)  last l = last_el(l) |
| ML | hlast_ml | add_info `dead_hdef` `hlast`;;
add_to_simpset `hol_to_nuprl` (lemma_to_cond_simp `hlast_nuprl` []) ;;
|
| DISP | hbutlast_df | butlast== butlast |
| ABS | hbutlast | butlast == l:'a List. but_last_el(l) |
| ML | hbutlast_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hbutlast");; add_info `d
irect_new_hdef` `hbutlast`;; |
| DISP | hlastn_df | lastn== lastn |
| ABS | hlastn | lastn == n: . l:'a List. lastn(n;l) |
| ML | hlastn_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hlastn");; add_info `dir
ect_old_hdef` `hlastn`;; |
| DISP | hbutlastn_df | butlastn== butlastn |
| ABS | hbutlastn | butlastn == n: . l:'a List. butlastn(n;l) |
| ML | hbutlastn_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hbutlastn");; add_info `
direct_new_hdef` `hbutlastn`;; |
| DISP | hell_df | ell== ell |
| ABS | hell | ell == n: . l:'a List. if n <z ||l|| then ell(n;l) else arb('a) fi |
| THM | hell_nuprl | 'a:S. n: . l:'a List. n < ||l||  ell n l = ell(n;l) |
| ML | hell_ml | add_info `dead_hdef` `hell`;;
add_to_simpset `hol_to_nuprl` (lemma_to_cond_simp `hell_nuprl` []) ;; |
| DISP | his_prefix_df | is_prefix== is_prefix |
| ABS | his_prefix | is_prefix ==
l1:'a List. l2:'a List. is_prefix(<eq_pred:( x:'a. y:'a. x
= y)>l1;l2) |
| ML | his_prefix_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "his_prefix");; add_info
`direct_new_hdef` `his_prefix`;; |
| DISP | his_suffix_df | is_suffix== is_suffix |
| ABS | his_suffix | is_suffix ==
l1:'a List. l2:'a List. is_suffix(<eq_pred:( x:'a. y:'a. x
= y)>l1;l2) |
| ML | his_suffix_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "his_suffix");; add_info
`direct_new_hdef` `his_suffix`;; |
| DISP | his_sublist_df | is_sublist== is_sublist |
| ABS | his_sublist | is_sublist ==
l1:'a List. l2:'a List. is_sublist(<eq_pred:( x:'a. y:'a. x
= y)>l1;l2) |
| ML | his_sublist_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "his_sublist");; add_info
`direct_new_hdef` `his_sublist`;; |
| DISP | hsplitp_df | splitp== splitp |
| ABS | hsplitp | splitp == P:'a  . l:'a List. splitp(P;l) |
| ML | hsplitp_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hsplitp");; add_info `di
rect_new_hdef` `hsplitp`;; |
| DISP | hprefix_df | prefix== prefix |
| ABS | hprefix | prefix == P:'a  . l:'a List. prefix(P;l) |
| ML | hprefix_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hprefix");; add_info `di
rect_new_hdef` `hprefix`;; |
| DISP | hsuffix_df | suffix== suffix |
| ABS | hsuffix | suffix == P:'a  . l:'a List. suffix(P;l) |
| ML | hsuffix_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hsuffix");; add_info `di
rect_new_hdef` `hsuffix`;; |
| DISP | hzip_df | zip== zip |
| ABS | hzip | zip == ll:'a List 'b List. let <l,l'> = ll in zip(l;l') |
| ML | hzip_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hzip");; add_info `direc
t_new_hdef` `hzip`;; |
| DISP | hunzip_df | unzip== unzip |
| ABS | hunzip | unzip == l:('a 'b) List. unzip(l) |
| ML | hunzip_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hunzip");; add_info `dir
ect_new_hdef` `hunzip`;; |
| DISP | hunzip_fst_df | unzip_fst== unzip_fst |
| ABS | hunzip_fst | unzip_fst == l:('a 'b) List. unzip_fst(l) |
| ML | hunzip_fst_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hunzip_fst");; add_info
`direct_new_hdef` `hunzip_fst`;; |
| DISP | hunzip_snd_df | unzip_snd== unzip_snd |
| ABS | hunzip_snd | unzip_snd == l:('a 'b) List. unzip_snd(l) |
| ML | hunzip_snd_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hunzip_snd");; add_info
`direct_new_hdef` `hunzip_snd`;; |
| DISP | hgenlist_df | genlist== genlist |
| ABS | hgenlist | genlist == f:  'a. n: . rev(genlist(f;n)) |
| ML | hgenlist_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hgenlist");; add_info `d
irect_new_hdef` `hgenlist`;; |
| DISP | hreplicate_df | replicate== replicate |
| ABS | hreplicate | replicate == n: . x:'a. replicate(n;x) |
| ML | hreplicate_ml | add_to_simpset `hol_to_nuprl` (hdef_to_simp "hreplicate");; add_info
`direct_new_hdef` `hreplicate`;; |
| COM | List_HOL_obligations | -------------- |
| THM | hsnoc_wf | 'a:S. snoc 'a  hlist{}('a)  hlist{}('a) |
| THM | hfoldr_wf | 'a,'b:S. foldr ('a  'b  'b)  'b  hlist{}('a)  'b |
| THM | hfoldl_wf | 'b,'a:S. foldl ('b  'a  'b)  'b  hlist{}('a)  'b |
| THM | hfilter_wf | 'a:S. filter ('a  hbool{})  hlist{}('a)  hlist{}('a) |
| THM | hscanl_wf | 'b,'a:S.
scanl ('b  'a  'b)  'b  hlist{}('a)  hlist{}('b) |
| THM | hscanr_wf | 'a,'b:S.
scanr ('a  'b  'b)  'b  hlist{}('a)  hlist{}('b) |
| THM | hreverse_wf | 'a:S. reverse hlist{}('a)  hlist{}('a) |
| THM | hall_el_wf | 'a:S. all_el ('a  hbool{})  hlist{}('a)  hbool{} |
| THM | hsome_el_wf | 'a:S. some_el ('a  hbool{})  hlist{}('a)  hbool{} |
| THM | his_el_wf | 'a:S. is_el 'a  hlist{}('a)  hbool{} |
| THM | hand_el_wf | and_el hlist{}(hbool{})  hbool{} |
| THM | hor_el_wf | or_el hlist{}(hbool{})  hbool{} |
| THM | hfirstn_wf | 'a:S. firstn hnum{}  hlist{}('a)  hlist{}('a) |
| THM | hbutfirstn_wf | 'a:S. butfirstn hnum{}  hlist{}('a)  hlist{}('a) |
| THM | hseg_wf | 'a:S. seg hnum{}  hnum{}  hlist{}('a)  hlist{}('a) |
| THM | hlast_wf | 'a:S. last hlist{}('a)  'a |
| THM | hbutlast_wf | 'a:S. butlast hlist{}('a)  hlist{}('a) |
| THM | hlastn_wf | 'a:S. lastn hnum{}  hlist{}('a)  hlist{}('a) |
| THM | hbutlastn_wf | 'a:S. butlastn hnum{}  hlist{}('a)  hlist{}('a) |
| THM | hell_wf | 'a:S. ell hnum{}  hlist{}('a)  'a |
| THM | his_prefix_wf | 'a:S. is_prefix hlist{}('a)  hlist{}('a)  hbool{} |
| THM | his_suffix_wf | 'a:S. is_suffix hlist{}('a)  hlist{}('a)  hbool{} |
| THM | his_sublist_wf | 'a:S. is_sublist hlist{}('a)  hlist{}('a)  hbool{} |
| THM | hsplitp_wf | 'a:S
splitp ('a  hbool{})
 hlist{}('a)
 hprod{}(hlist{}('a); hlist{}('a)) |
| THM | hprefix_wf | 'a:S. prefix ('a  hbool{})  hlist{}('a)  hlist{}('a) |
| THM | hsuffix_wf | 'a:S. suffix ('a  hbool{})  hlist{}('a)  hlist{}('a) |
| THM | hzip_wf | 'a,'b:S.
zip hprod{}(hlist{}('a); hlist{}('b))  hlist{}(hprod{}('a; 'b)) |
| THM | hunzip_wf | 'a,'b:S.
unzip hlist{}(hprod{}('a; 'b))
 hprod{}(hlist{}('a); hlist{}('b)) |
| THM | hunzip_fst_wf | 'a,'b:S. unzip_fst hlist{}(hprod{}('a; 'b))  hlist{}('a) |
| THM | hunzip_snd_wf | 'a,'b:S. unzip_snd hlist{}(hprod{}('a; 'b))  hlist{}('b) |
| THM | hgenlist_wf | 'a:S. genlist (hnum{}  'a)  hnum{}  hlist{}('a) |
| THM | hreplicate_wf | 'a:S. replicate hnum{}  'a  hlist{}('a) |
| THM | hsnoc_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))))))) |
| THM | hfoldr_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)))))))) |
| THM | hfoldl_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))))))) |
| THM | hfilter_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))))))) |
| THM | hscanl_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)))))))) |
| THM | hscanr_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)))))))) |
| THM | reverse_snoc_lemma | 'a:S. x:'a. l:'a List. snoc(x;l) = l @ (x::[]) |
| THM | hreverse_wd | 'a:S
(and (equal (reverse nil) nil)
(all
( x:'a. all
( l:hlist{}('a). equal (reverse (cons x l)) (snoc x (reverse l)))))) |
| THM | hall_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))))))) |
| THM | hsome_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))))))) |
| THM | his_el_def | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (is_el x l) (some_el (equal x) l)))) |
| THM | hand_el_def | (equal and_el (all_el i)) |
| THM | hor_el_def | (equal or_el (some_el i)) |
| THM | hfirstn_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))))))) |
| THM | hbutfirstn_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)))))) |
| THM | hseg_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)))))))) |
| THM | hlast_def | 'a:S
(all
( l:hlist{}('a). equal (last l) (hd (seg 1 (pre (length l)) l)))) |
| THM | hbutlast_def | 'a:S
(all
( l:hlist{}('a). equal (butlast l) (seg (pre (length l)) 0 l))) |
| THM | hlastn_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))))))) |
| THM | hbutlastn_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)))))) |
| THM | hell_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)))))) |
| ML | reverse_append_simp | add_lemma_simp `reverse_append` ;; |
| ML | and_or_simps | map add_lemma_simp
``and_true true_and and_false false_and
or_true true_or or_false false_or``
;; |
| THM | his_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))))))))) |
| THM | his_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))))))))) |
| THM | his_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)))))))))) |
| THM | hsplitp_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))))))))) |
| THM | hprefix_def | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}('a). equal (prefix P l) (fst (splitp (o not P) l))))) |
| ML | spread_simp | add_simp
(`spread2`,
`spread`,
(\e t. is_spread_term t & is_pair_term (subterm t 1)),
RedexC
)
;; |
| THM | hsuffix_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)))) |
| THM | hzip_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))))))))) |
| THM | hunzip_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)))))))) |
| THM | hunzip_fst_def | 'a,'b:S.
(all
( l:hlist{}(hprod{}('a; 'b)). equal (unzip_fst l) (fst (unzip l)))) |
| THM | hunzip_snd_def | 'a,'b:S.
(all
( l:hlist{}(hprod{}('a; 'b)). equal (unzip_snd l) (snd (unzip l)))) |
| THM | hgenlist_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)))))) |
| THM | hreplicate_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)))))) |
| COM | List_HOL_theorems | -------------- |
| THM | hlist_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)))) |
| THM | hnull_def_2 | 'a:S
(and (equal (null nil) t)
(all ( x:'a. all ( l:hlist{}('a). equal (null (cons x l)) f)))) |
| THM | hhd_wd_2 | 'a:S. (all ( x:'a. all ( l:hlist{}('a). equal (hd (cons x l)) x))) |
| THM | htl_wd_2 | 'a:S. (all ( x:'a. all ( l:hlist{}('a). equal (tl (cons x l)) l))) |
| THM | happend_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))))))) |
| THM | hflat_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)))))) |
| THM | hlength_wd_2 | 'a:S
(and (equal (length nil) 0)
(all
( x:'a. all
( l:hlist{}('a). equal (length (cons x l)) (suc (length l)))))) |
| THM | hmap_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))))))) |
| THM | hmap2_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))))))))) |
| THM | hel_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)))))) |
| THM | hsum_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)))))) |
| THM | hnull_char_2 | 'a:S
(and (null nil)
(all ( x:'a. all ( l:hlist{}('a). not (null (cons x l)))))) |
| THM | hlist_cases_2 | 'a:S
(all
( l:hlist{}('a). or (equal l nil)
(exists ( l':hlist{}('a). exists ( x:'a. equal l (cons x l')))))) |
| THM | hcons_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'))))))) |
| THM | hnot_nil_cons_2 | 'a:S
(all ( x:'a. all ( l:hlist{}('a). not (equal nil (cons x l))))) |
| THM | hnot_cons_nil_2 | 'a:S
(all ( x:'a. all ( l:hlist{}('a). not (equal (cons x l) nil)))) |
| THM | hlist_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)))))))) |
| THM | hnot_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)))))))) |
| THM | heq_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)))))))) |
| THM | hcons_wd_2 | 'a:S
(all
( l:hlist{}('a). implies (not (null l))
(equal (cons (hd l) (tl l)) l))) |
| THM | happend_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))))) |
| THM | hlength_append_3 | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). equal (length (append l1 l2))
(add (length l1) (length l2))))) |
| THM | hmap_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)))))) |
| THM | hlength_map_2 | 'b,'a:S.
(all
( l:hlist{}('a). all
( f:'a  'b. equal (length (map f l)) (length l)))) |
| THM | hlength_nil_3 | 'a:S
(all ( l:hlist{}('a). equal (equal (length l) 0) (equal l nil))) |
| THM | hlength_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')))))))) |
| THM | hlength_eq_nil_2 | 'a:S
(all
( P:hlist{}('a)  hbool{}. equal
(all ( l:hlist{}('a). implies (equal (length l) 0) (P l)))
(P nil))) |
| THM | hlength_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))))))) |
| THM | hnull_eq_nil | 'a:S. (all ( l:hlist{}('a). equal (null l) (equal l nil))) |
| THM | hlength_eq | 'a:S
(all
( x:hlist{}('a). all
( y:hlist{}('a). implies (equal x y)
(equal (length x) (length y))))) |
| THM | hlength_not_null | 'a:S. (all ( l:hlist{}('a). equal (lt 0 (length l)) (not (null l)))) |
| THM | hreverse_snoc | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (reverse (snoc x l)) (cons x (reverse l))))) |
| THM | hreverse_reverse | 'a:S. (all ( l:hlist{}('a). equal (reverse (reverse l)) l)) |
| THM | hsnoc_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)))))))) |
| THM | hsnoc_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)))) |
| THM | hsnoc_cases | 'a:S
(all
( l:hlist{}('a). or (equal l nil)
(exists ( l':hlist{}('a). exists ( x:'a. equal l (snoc x l')))))) |
| THM | hlength_snoc | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (length (snoc x l)) (suc (length l))))) |
| THM | hnot_nil_snoc | 'a:S
(all ( x:'a. all ( l:hlist{}('a). not (equal nil (snoc x l))))) |
| THM | hnot_snoc_nil | 'a:S
(all ( x:'a. all ( l:hlist{}('a). not (equal (snoc x l) nil)))) |
| THM | hsnoc_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'))))))) |
| THM | hsnoc_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))))))) |
| THM | hsnoc_reverse_cons | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (snoc x l) (reverse (cons x (reverse l)))))) |
| THM | hsnoc_append | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (snoc x l) (append l (cons x nil))))) |
| THM | hmap_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)))))) |
| THM | hfoldr_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)))))) |
| THM | hfoldl_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)))))) |
| THM | hfoldr_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)))))) |
| THM | hlength_foldr | 'a:S
(all
( l:hlist{}('a). equal (length l)
(foldr ( x:'a. l':hnum{}. suc l') 0 l))) |
| THM | hlength_foldl | 'a:S
(all
( l:hlist{}('a). equal (length l)
(foldl ( l':hnum{}. x:'a. suc l') 0 l))) |
| THM | hmap_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)))) |
| THM | hmap_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)))) |
| THM | hmap_o_2 | 'c,'a,'b:S.
(all
( f:'b  'c. all
( g:'a  'b. equal (map (o f g)) (o (map f) (map g))))) |
| THM | hmap_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))))) |
| THM | hfilter_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)))) |
| THM | hfilter_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)))))) |
| THM | hfilter_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)))) |
| THM | hfilter_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)))))) |
| THM | hfilter_idem | 'a:S
(all
( f:'a  hbool{}. all
( l:hlist{}('a). equal (filter f (filter f l)) (filter f l)))) |
| THM | hfilter_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)))))) |
| THM | hlength_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))))) |
| THM | happend_nil | 'a:S
(and (all ( l:hlist{}('a). equal (append l nil) l))
(all ( l:hlist{}('a). equal (append nil l) l))) |
| THM | happend_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)))))) |
| THM | hreverse_append_2 | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). equal (reverse (append l1 l2))
(append (reverse l2) (reverse l1))))) |
| THM | happend_foldr | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). equal (append l1 l2) (foldr cons l2 l1)))) |
| THM | happend_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)))) |
| THM | hfoldr_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)))))) |
| THM | hfoldl_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)))))) |
| THM | hcons_append | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (cons x l) (append (cons x nil) l)))) |
| THM | hassoc_append | 'a:S. (assoc append) |
| THM | hmonoid_append_nil | 'a:S. (monoid append nil) |
| THM | happend_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'))))))))) |
| THM | hfilter_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)))))) |
| THM | hflat_snoc | 'a:S
(all
( x:hlist{}('a). all
( l:hlist{}(hlist{}('a)). equal (flat (snoc x l))
(append (flat l) x)))) |
| THM | hflat_foldr | 'a:S
(all
( l:hlist{}(hlist{}('a)). equal (flat l) (foldr append nil l))) |
| THM | hflat_foldl | 'a:S
(all
( l:hlist{}(hlist{}('a)). equal (flat l) (foldl append nil l))) |
| THM | hlength_flat | 'a:S
(all
( l:hlist{}(hlist{}('a)). equal (length (flat l))
(it_sum (map length l)))) |
| THM | hreverse_foldr | 'a:S. (all ( l:hlist{}('a). equal (reverse l) (foldr snoc nil l))) |
| THM | hreverse_foldl | 'a:S
(all
( l:hlist{}('a). equal (reverse l)
(foldl ( l':hlist{}('a). x:'a. cons x l') nil l))) |
| THM | hlength_reverse | 'a:S. (all ( l:hlist{}('a). equal (length (reverse l)) (length l))) |
| THM | hreverse_eq_nil | 'a:S
(all ( l:hlist{}('a). equal (equal (reverse l) nil) (equal l nil))) |
| THM | hall_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)))))) |
| THM | hall_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)))))) |
| THM | hall_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))))) |
| THM | hall_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)))))) |
| THM | hsome_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)))))) |
| THM | hnot_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)))) |
| THM | hnot_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)))) |
| THM | his_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))))))) |
| THM | his_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)))))) |
| THM | hsum_snoc | (all
( x:hnum{}. all
( l:hlist{}(hnum{}). equal (it_sum (snoc x l)) (add (it_sum l) x)))) |
| THM | hsum_foldr | (all ( l:hlist{}(hnum{}). equal (it_sum l) (foldr add 0 l))) |
| THM | hsum_foldl | (all ( l:hlist{}(hnum{}). equal (it_sum l) (foldl add 0 l))) |
| THM | his_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)))))) |
| THM | his_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)))))) |
| THM | his_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')))))))) |
| THM | his_prefix_is_sublist | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). implies (is_prefix l1 l2) (is_sublist l1 l2)))) |
| THM | his_suffix_is_sublist | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). implies (is_suffix l1 l2) (is_sublist l1 l2)))) |
| THM | his_prefix_reverse | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). equal (is_prefix (reverse l1) (reverse l2))
(is_suffix l1 l2)))) |
| THM | his_suffix_reverse | 'a:S
(all
( l2:hlist{}('a). all
( l1:hlist{}('a). equal (is_suffix (reverse l1) (reverse l2))
(is_prefix l1 l2)))) |
| THM | his_sublist_reverse | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). equal (is_sublist (reverse l1) (reverse l2))
(is_sublist l1 l2)))) |
| THM | hprefix_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)))) |
| THM | hprefix_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)))))) |
| THM | his_prefix_prefix | 'a:S
(all
( P:'a  hbool{}. all ( l:hlist{}('a). is_prefix l (prefix P l)))) |
| THM | hlength_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)))))) |
| THM | hlength_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)))))) |
| THM | hcomm_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))))))))) |
| THM | hcomm_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))))))))) |
| THM | hfcomm_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)))))))))) |
| THM | hfcomm_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)))))))))) |
| THM | hfoldl_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))))) |
| THM | hfoldr_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))))) |
| THM | hfoldr_cons_nil | 'a:S. (all ( l:hlist{}('a). equal (foldr cons nil l) l)) |
| THM | hfoldl_snoc_nil | 'a:S
(all
( l:hlist{}('a). equal
(foldl ( xs:hlist{}('a). x:'a. snoc x xs) nil l)
l)) |
| THM | hfoldr_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)))))) |
| THM | hfoldl_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)))))) |
| THM | hfoldr_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))))) |
| THM | hfoldl_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))))) |
| THM | hfoldr_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)))))) |
| THM | hfoldl_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)))))) |
| THM | hall_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)))) |
| THM | hall_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)))) |
| THM | hsome_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)))) |
| THM | hsome_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)))) |
| THM | hall_el_foldr_map | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}('a). equal (all_el P l) (foldr and t (map P l))))) |
| THM | hall_el_foldl_map | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}('a). equal (all_el P l) (foldl and t (map P l))))) |
| THM | hsome_el_foldr_map | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}('a). equal (some_el P l) (foldr or f (map P l))))) |
| THM | hsome_el_foldl_map | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}('a). equal (some_el P l) (foldl or f (map P l))))) |
| THM | hfoldr_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)))))) |
| THM | hfoldl_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)))))) |
| THM | hassoc_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)))))))) |
| THM | hassoc_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)))))))) |
| THM | hmap_flat | 'a,'b:S.
(all
( f:'a  'b. all
( l:hlist{}(hlist{}('a)). equal (map f (flat l))
(flat (map (map f) l))))) |
| THM | hfilter_flat | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}(hlist{}('a)). equal (filter P (flat l))
(flat (map (filter P) l))))) |
| THM | hsome_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))))) |
| THM | hsome_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)))))) |
| THM | hsome_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)))))) |
| THM | his_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)))))) |
| THM | his_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)))) |
| THM | his_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)))) |
| THM | hnull_foldr | 'a:S
(all
( l:hlist{}('a). equal (null l)
(foldr ( x:'a. l':hbool{}. f) t l))) |
| THM | hnull_foldl | 'a:S
(all
( l:hlist{}('a). equal (null l)
(foldl ( x:hbool{}. l':'a. f) t l))) |
| THM | hmap_reverse | 'a,'b:S.
(all
( f:'a  'b. all
( l:hlist{}('a). equal (map f (reverse l)) (reverse (map f l))))) |
| THM | hfilter_reverse | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}('a). equal (filter P (reverse l))
(reverse (filter P l))))) |
| THM | hlast_char | 'a:S. (all ( x:'a. all ( l:hlist{}('a). equal (last (snoc x l)) x))) |
| THM | hbutlast_char | 'a:S
(all ( x:'a. all ( l:hlist{}('a). equal (butlast (snoc x l)) l))) |
| THM | hseg_length_id | 'a:S. (all ( l:hlist{}('a). equal (seg (length l) 0 l) l)) |
| THM | hseg_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)))))) |
| THM | hseg_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)))))) |
| THM | hbutlastn_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))))) |
| THM | hlastn_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)))))) |
| THM | hlength_lastn | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (length (lastn n l)) n)))) |
| THM | hlastn_length_id | 'a:S. (all ( l:hlist{}('a). equal (lastn (length l) l) l)) |
| THM | hlastn_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))))))) |
| THM | hfirstn_length_id | 'a:S. (all ( l:hlist{}('a). equal (firstn (length l) l) l)) |
| THM | hfirstn_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)))))) |
| THM | hbutlastn_length_nil | 'a:S. (all ( l:hlist{}('a). equal (butlastn (length l) l) nil)) |
| THM | hbutlastn_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)))))) |
| THM | hbutlastn_butlast | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (lt n (length l))
(equal (butlastn n (butlast l)) (butlast (butlastn n l)))))) |
| THM | hlength_butlastn | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (length (butlastn n l)) (sub (length l) n))))) |
| THM | hbutlastn_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)))))) |
| THM | happend_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)))) |
| THM | happend_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))))) |
| THM | hbutlastn_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))))))) |
| THM | hbutlastn_length_append | 'a:S
(all
( l2:hlist{}('a). all
( l1:hlist{}('a). equal (butlastn (length l2) (append l1 l2)) l1))) |
| THM | hlastn_length_append | 'a:S
(all
( l2:hlist{}('a). all
( l1:hlist{}('a). equal (lastn (length l2) (append l1 l2)) l2))) |
| THM | hbutlastn_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))))))) |
| THM | hbutlastn_length_cons | 'a:S
(all
( l:hlist{}('a). all
( x:'a. equal (butlastn (length l) (cons x l)) (cons x nil)))) |
| THM | hlast_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)))))) |
| THM | hbutlastn_lastn_nil | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (butlastn n (lastn n l)) nil)))) |
| THM | hlastn_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))))))) |
| THM | hbutlastn_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))))))) |
| THM | hlastn_1 | 'a:S
(all
( l:hlist{}('a). implies (not (equal l nil))
(equal (lastn 1 l) (cons (last l) nil)))) |
| THM | hbutlastn_1 | 'a:S
(all
( l:hlist{}('a). implies (not (equal l nil))
(equal (butlastn 1 l) (butlast l)))) |
| THM | hbutlastn_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)))))) |
| THM | hlastn_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)))))) |
| THM | hlastn_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)))))) |
| THM | hlastn_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))))))) |
| THM | hbutlastn_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))))))) |
| THM | hall_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))))))) |
| THM | hall_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))))))) |
| THM | hlength_firstn_2 | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (length (firstn n l)) n)))) |
| THM | hfirstn_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))))))) |
| THM | hlength_butfirstn | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (length (butfirstn n l)) (sub (length l) n))))) |
| THM | hbutfirstn_length_nil | 'a:S. (all ( l:hlist{}('a). equal (butfirstn (length l) l) nil)) |
| THM | hbutfirstn_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)))))) |
| THM | hbutfirstn_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)))))) |
| THM | hbutfirstn_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)))))) |
| THM | happend_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)))) |
| THM | hlastn_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))))) |
| THM | hfirstn_seg | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (firstn n l) (seg n 0 l))))) |
| THM | hbutfirstn_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))))) |
| THM | happend_butlast_last | 'a:S
(all
( l:hlist{}('a). implies (not (equal l nil))
(equal (append (butlast l) (cons (last l) nil)) l))) |
| THM | hbutfirstn_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))))))) |
| THM | happend_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))))) |
| THM | hseg_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)))))))) |
| THM | hseg_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))))))) |
| THM | hseg_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))))))) |
| THM | hseg_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))))))) |
| THM | hseg_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)))))))) |
| THM | hseg_length_snoc | 'a:S
(all
( l:hlist{}('a). all
( x:'a. equal (seg 1 (length l) (snoc x l)) (cons x nil)))) |
| THM | hseg_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))))))) |
| THM | hell_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)))))) |
| THM | hsnoc_foldr | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (snoc x l) (foldr cons (cons x nil) l)))) |
| THM | his_el_foldr_map | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (is_el x l) (foldr or f (map (equal x) l))))) |
| THM | his_el_foldl_map | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (is_el x l) (foldl or f (map (equal x) l))))) |
| THM | hfilter_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))))) |
| THM | hfcomm_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))))))))) |
| THM | hfcomm_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))))))))) |
| THM | hfoldr_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)))))))) |
| THM | hfoldr_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)))))))) |
| THM | hcomm_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))))))) |
| THM | hcomm_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))))))) |
| THM | hell_last | 'a:S
(all
( l:hlist{}('a). implies (not (null l)) (equal (ell 0 l) (last l)))) |
| THM | hell_0_snoc | 'a:S
(all ( l:hlist{}('a). all ( x:'a. equal (ell 0 (snoc x l)) x))) |
| THM | hell_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)))))) |
| THM | hell_suc_snoc | 'a:S
(all
( n:hnum{}. all
( x:'a. all
( l:hlist{}('a). equal (ell (suc n) (snoc x l)) (ell n l))))) |
| THM | hell_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)))))) |
| THM | hell_length_cons | 'a:S
(all
( l:hlist{}('a). all ( x:'a. equal (ell (length l) (cons x l)) x))) |
| THM | hell_length_snoc | 'a:S
(all
( l:hlist{}('a). all
( x:'a. equal (ell (length l) (snoc x l))
(cond (null l) x (hd l))))) |
| THM | hell_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)))))) |
| THM | hell_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)))))) |
| THM | hell_pre_length | 'a:S
(all
( l:hlist{}('a). implies (not (equal l nil))
(equal (ell (pre (length l)) l) (hd l)))) |
| THM | hel_length_snoc | 'a:S
(all
( l:hlist{}('a). all ( x:'a. equal (el (length l) (snoc x l)) x))) |
| THM | hel_pre_length | 'a:S
(all
( l:hlist{}('a). implies (not (equal l nil))
(equal (el (pre (length l)) l) (last l)))) |
| THM | hel_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)))))) |
| THM | hel_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))))) |
| THM | hel_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))))) |
| THM | hell_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))))) |
| THM | hell_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))))))) |
| THM | hlength_butlast | 'a:S
(all
( l:hlist{}('a). implies (not (equal l nil))
(equal (length (butlast l)) (pre (length l))))) |
| THM | hbutfirstn_length_append | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). equal (butfirstn (length l1) (append l1 l2)) l2))) |
| THM | hfirstn_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)))))) |
| THM | hfirstn_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))))))) |
| THM | hfirstn_length_append | 'a:S
(all
( l1:hlist{}('a). all
( l2:hlist{}('a). equal (firstn (length l1) (append l1 l2)) l1))) |
| THM | hreverse_flat | 'a:S
(all
( l:hlist{}(hlist{}('a)). equal (reverse (flat l))
(flat (reverse (map reverse l))))) |
| THM | hmap_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))))))) |
| THM | hflat_append | 'a:S
(all
( l1:hlist{}(hlist{}('a)). all
( l2:hlist{}(hlist{}('a)). equal (flat (append l1 l2))
(append (flat l1) (flat l2))))) |
| THM | hflat_reverse | 'a:S
(all
( l:hlist{}(hlist{}('a)). equal (flat (reverse l))
(reverse (flat (map reverse l))))) |
| THM | hflat_flat | 'a:S
(all
( l:hlist{}(hlist{}(hlist{}('a))). equal (flat (flat l))
(flat (map flat l)))) |
| THM | hall_el_reverse | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}('a). equal (all_el P (reverse l)) (all_el P l)))) |
| THM | hsome_el_reverse | 'a:S
(all
( P:'a  hbool{}. all
( l:hlist{}('a). equal (some_el P (reverse l)) (some_el P l)))) |
| THM | hall_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)))))))) |
| THM | hall_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))))))) |
| THM | hall_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))))))) |
| THM | hsome_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))))))) |
| THM | hsome_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)))))) |
| THM | hsome_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)))))) |
| THM | hsome_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)))))) |
| THM | hsome_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)))))) |
| THM | his_el_reverse | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (is_el x (reverse l)) (is_el x l)))) |
| THM | his_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)))))) |
| THM | his_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))))))) |
| THM | his_el_some_el | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (is_el x l) (some_el (equal x) l)))) |
| THM | his_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)))))) |
| THM | his_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)))))) |
| THM | his_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)))))) |
| THM | his_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)))))) |
| THM | hzip_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))))))))) |
| THM | hunzip_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))))))) |
| THM | hlength_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)))))) |
| THM | hlength_unzip_fst | 'a,'b:S.
(all
( l:hlist{}(hprod{}('a; 'b)). equal (length (unzip_fst l))
(length l))) |
| THM | hlength_unzip_snd | 'a,'b:S.
(all
( l:hlist{}(hprod{}('a; 'b)). equal (length (unzip_snd l))
(length l))) |
| THM | hzip_unzip | 'a,'b:S.
(all ( l:hlist{}(hprod{}('a; 'b)). equal (zip (unzip l)) l)) |
| THM | hunzip_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))))) |
| THM | hsum_append | (all
( l1:hlist{}(hnum{}). all
( l2:hlist{}(hnum{}). equal (it_sum (append l1 l2))
(add (it_sum l1) (it_sum l2))))) |
| THM | hsum_reverse | (all ( l:hlist{}(hnum{}). equal (it_sum (reverse l)) (it_sum l))) |
| THM | hsum_flat | (all
( l:hlist{}(hlist{}(hnum{})). equal (it_sum (flat l))
(it_sum (map it_sum l)))) |
| THM | hel_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)))))) |
| THM | hel_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)))))) |
| THM | hel_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))))))) |
| THM | hel_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)))))) |
| THM | hel_seg | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (lt n (length l))
(equal (el n l) (hd (seg 1 n l)))))) |
| THM | hel_is_el | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (lt n (length l)) (is_el (el n l) l)))) |
| THM | htl_snoc | 'a:S
(all
( x:'a. all
( l:hlist{}('a). equal (tl (snoc x l))
(cond (null l) nil (snoc x (tl l)))))) |
| THM | hel_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))))) |
| THM | hel_reverse_ell | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (lt n (length l))
(equal (el n (reverse l)) (ell n l))))) |
| THM | hell_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))))) |
| THM | hell_is_el | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (lt n (length l)) (is_el (el n l) l)))) |
| THM | hell_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))))) |
| THM | hell_reverse_el | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (lt n (length l))
(equal (ell n (reverse l)) (el n l))))) |
| THM | hfirstn_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))))) |
| THM | hbutlastn_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))))) |
| THM | hlastn_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))))) |
| THM | hbutfirstn_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))))) |
| THM | hseg_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))))))) |
| THM | hbutfirstn_reverse | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (butfirstn n (reverse l)) (reverse (butlastn n l)))))) |
| THM | hbutlastn_reverse | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (butlastn n (reverse l)) (reverse (butfirstn n l)))))) |
| THM | hlastn_reverse | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (lastn n (reverse l)) (reverse (firstn n l)))))) |
| THM | hfirstn_reverse | 'a:S
(all
( n:hnum{}. all
( l:hlist{}('a). implies (le n (length l))
(equal (firstn n (reverse l)) (reverse (lastn n l)))))) |
| THM | hseg_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))))))) |
| THM | hlength_genlist | 'a:S
(all
( f:hnum{}  'a. all ( n:hnum{}. equal (length (genlist f n)) n))) |
| THM | hlength_replicate | 'a:S
(all ( n:hnum{}. all ( x:'a. equal (length (replicate n x)) n))) |
| THM | his_el_replicate | 'a:S
(all
( n:hnum{}. implies (lt 0 n)
(all ( x:'a. is_el x (replicate n x))))) |
| THM | hall_el_replicate | 'a:S
(all ( x:'a. all ( n:hnum{}. all_el (equal x) (replicate n x)))) |
| THM | hand_el_foldl | (all ( l:hlist{}(hbool{}). equal (and_el l) (foldl and t l))) |
| THM | hand_el_foldr | (all ( l:hlist{}(hbool{}). equal (and_el l) (foldr and t l))) |
| THM | hor_el_foldl | (all ( l:hlist{}(hbool{}). equal (or_el l) (foldl or f l))) |
| THM | hor_el_foldr | (all ( l:hlist{}(hbool{}). equal (or_el l) (foldr or f l))) |
| THM | hmap2_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)))))))) |
| COM | List_Nuprl_theorems | -------------- |
| THM | foldr_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)) |
| THM | foldl_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)) |
| THM | filter_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 ) |
| THM | scanl_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))) |
| THM | scanr_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))) |
| THM | reverse_wd | 'a:S
[] = [] ( x:'a. l:'a List. rev(l) @ (x::[]) = snoc(x;rev(l))) |
| THM | all_el_wd | 'a:S
( P:'a  . True)
( P:'a  . x:'a. l:'a List.
P x  every(P;l) = P x  every(P;l)) |
| THM | some_el_wd | 'a:S
( P:'a  . True)
( P:'a  . x:'a. l:'a List.
(P x)  some(P;l) = (P x)  some(P;l)) |
| THM | is_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) |
| THM | is_el_def__old1 | 'a:S. eq:eq('a). x:'a. l:'a List.
(x _{eq} l)   some( y:'a. x = y;l) |
| THM | is_el_def | 'a:S. eq:eq('a). x:'a. l:'a List.
x _{eq} l = some( y:'a. x = y;l) |
| THM | and_el_def | ( l: List. and_el(l)) = ( l: List. every( x: . x;l)) |
| THM | or_el_def | ( l: List. or_el(l)) = ( l: List. some( x: . x;l)) |
| THM | firstn_wd | 'a:S
( l:'a List. firstn(0;l) = [])
( n: . x:'a. l:'a List. firstn(n + 1;x::l) = (x::firstn(n;l))) |
| THM | butfirstn_wd | 'a:S
( l:'a List. l = l)
( n: . x:'a. l:'a List. nth_tl(n + 1;x::l) = nth_tl(n;l)) |
| THM | seg_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)) |
| THM | last_def | 'a:S. l:'a List. mt(l)  last_el(l) = head(seg(1;||l|| - 1;l)) |
| THM | butlast_def | 'a:S. l:'a List. mt(l)  but_last_el(l) = seg(||l|| - 1;0;l) |
| THM | lastn_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))) |
| THM | butlastn_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)) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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)) |
| THM | splitp_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 ) |
| THM | prefix_def | 'a:S. P:'a  . l:'a List.
prefix(P;l) = splitp(( p: .  p) o P;l).1 |
| THM | suffix_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) |
| THM | zip_wd | 'a,'b:S.
[] = []
( x1:'a. l1:'a List. x2:'b. l2:'b List.
(<x1, x2>::zip(l1;l2)) = (<x1, x2>::zip(l1;l2))) |
| THM | unzip_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)>) |
| THM | unzip_fst_def | 'a,'b:S. l:('a 'b) List. unzip_fst(l) = unzip(l).1 |
| THM | unzip_snd_def | 'a,'b:S. l:('a 'b) List. unzip_snd(l) = unzip(l).2 |
| THM | genlist_wd | 'a:S
( f:  'a. rev(genlist(f;0)) = [])
( f:  'a. n: .
rev(genlist(f;n + 1)) = snoc(f n;rev(genlist(f;n)))) |
| THM | replicate_wd | 'a:S
( x:'a. replicate(0;x) = [])
( n: . x:'a. replicate(n + 1;x) = (x::replicate(n;x))) |
| THM | list_induct_2 | 'a:S. P:'a List  .
(P []) ( l:'a List. (P l)  ( x:'a. (P (x::l))))
 ( l:'a List. (P l)) |
| THM | null_def_2 | 'a:S. x:'a. l:'a List. True |
| THM | hd_wd_2 | 'a:S. x:'a. l:'a List. x = x |
| THM | tl_wd_2 | 'a:S. x:'a. l:'a List. l = l |
| THM | append_wd_2 | 'a:S
( l:'a List. l = l)
( l1,l2:'a List. x:'a. (x::(l1 @ l2)) = (x::(l1 @ l2))) |
| THM | flat_wd_2 | 'a:S
[] = []
( x:'a List. l:'a List List. x @ flatten(l) = x @ flatten(l)) |
| THM | length_wd_2 | 'a:S. 0 = 0 ( x:'a. l:'a List. ||l|| + 1 = ||l|| + 1) |
| THM | map_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))) |
| THM | map2_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))) |
| THM | sum_els_wd_2 | 0 = 0 ( x: . l: List. x + it_sum(l) = x + it_sum(l)) |
| THM | null_char_2 | 'a:S. x:'a. l:'a List. True |
| THM | list_cases_2 | 'a:S. l:'a List. l = [] ( l':'a List. x:'a. l = (x::l')) |
| THM | not_nil_cons_2 | 'a:S. x:'a. l:'a List. ([] = (x::l)) |
| THM | not_cons_nil_2 | 'a:S. x:'a. l:'a List. ((x::l) = []) |
| THM | list_not_eq_2 | 'a:S. l1,l2:'a List.
(l1 = l2)  ( x1,x2:'a. ((x1::l1) = (x2::l2))) |
| THM | not_eq_list_2 | 'a:S. x1,x2:'a.
(x1 = x2)  ( l1,l2:'a List. ((x1::l1) = (x2::l2))) |
| THM | eq_list_2 | 'a:S. x1,x2:'a.
x1 = x2  ( l1,l2:'a List. l1 = l2  (x1::l1) = (x2::l2)) |
| THM | cons_wd_2 | 'a:S. l:'a List. mt(l)  ((hd l)::tl(l)) = l |
| THM | append_assoc_3 | 'a:S. l1,l2,l3:'a List. l1 @ l2 @ l3 = (l1 @ l2) @ l3 |
| THM | length_append_3 | 'a:S. l1,l2:'a List. ||l1 @ l2|| = ||l1|| + ||l2|| |
| THM | map_append_3 | 'a,'b:S. f:'a  'b. l1,l2:'a List.
map(f;l1 @ l2) = map(f;l1) @ map(f;l2) |
| THM | length_map_2 | 'b,'a:S. l:'a List. f:'a  'b. ||map(f;l)|| = ||l|| |
| THM | length_nil_3 | 'a:S. l:'a List. ||l|| = 0   l = [] |
| THM | length_cons_3 | 'a:S. l:'a List. n: .
||l|| = n + 1   ( x:'a. l':'a List. ||l'|| = n l = (x::l')) |
| THM | length_eq_nil_2 | 'a:S. P:'a List  . ( l:'a List. ||l|| = 0  (P l))   (P []) |
| THM | length_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||) |
| THM | null_eq_nil | 'a:S. l:'a List. mt(l)   l = [] |
| THM | length_eq | 'a:S. x,y:'a List. x = y  ||x|| = ||y|| |
| THM | length_not_null | 'a:S. l:'a List. 0 < ||l||   mt(l) |
| THM | reverse_snoc | 'a:S. x:'a. l:'a List. rev(snoc(x;l)) = (x::rev(l)) |
| THM | reverse_reverse | 'a:S. l:'a List. rev(rev(l)) = l |
| THM | snoc_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) |
| THM | snoc_induct | 'a:S. P:'a List  .
(P []) ( l:'a List. (P l)  ( x:'a. (P snoc(x;l))))
 ( l:'a List. (P l)) |
| THM | snoc_cases | 'a:S. l:'a List. l = [] ( l':'a List. x:'a. l = snoc(x;l')) |
| THM | length_snoc | 'a:S. x:'a. l:'a List. ||snoc(x;l)|| = ||l|| + 1 |
| THM | not_nil_snoc | 'a:S. x:'a. l:'a List. ([] = snoc(x;l)) |
| THM | not_snoc_nil | 'a:S. x:'a. l:'a List. (snoc(x;l) = []) |
| THM | snoc_11_2 | 'a:S. x:'a. l:'a List. x':'a. l':'a List.
snoc(x;l) = snoc(x';l') = x = x'  l = l' |
| THM | snoc_11 | 'a:S. x:'a. l:'a List. x':'a. l':'a List.
snoc(x;l) = snoc(x';l')   x = x' l = l' |
| THM | snoc_eq_length_eq | 'a:S. x1:'a. l1:'a List. x2:'a. l2:'a List.
snoc(x1;l1) = snoc(x2;l2)  ||l1|| = ||l2|| |
| THM | snoc_reverse_cons | 'a:S. x:'a. l:'a List. snoc(x;l) = rev(rev(l)) @ (x::[]) |
| THM | snoc_append | 'a:S. x:'a. l:'a List. snoc(x;l) = l @ (x::[]) |
| THM | map_snoc | 'a,'b:S. f:'a  'b. x:'a. l:'a List.
map(f;snoc(x;l)) = snoc(f x;map(f;l)) |
| THM | foldr_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) |
| THM | foldl_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 |
| THM | foldr_foldl | 'a:S. f:'a  'a  'a. e:'a.
monoid('a;f;e)  ( l:'a List. foldr(f;e;l) = foldl(f;e;l)) |
| THM | length_foldr | 'a:S. l:'a List. ||l|| = foldr( x:'a. l': . l' + 1;0;l) |
| THM | length_foldl | 'a:S. l:'a List. ||l|| = foldl( l': . x:'a. l' + 1;0;l) |
| THM | map_foldr | 'a,'b:S. f:'a  'b. l:'a List.
map(f;l) = foldr( x:'a. l':'b List. (f x)::l';[];l) |
| THM | map_foldl | 'a,'b:S. f:'a  'b. l:'a List.
map(f;l) = foldl( l':'b List. x:'a. snoc(f x;l');[];l) |
| THM | map_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)) |
| THM | map_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) |
| THM | filter_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) |
| THM | filter_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 |
| THM | filter_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) |
| THM | filter_comm | 'a:S. f1,f2:'a  . l:'a List.
filter(f1;filter(f2;l)) = filter(f2;filter(f1;l)) |
| THM | filter_idem | 'a:S. f:'a  . l:'a List. filter(f;filter(f;l)) = filter(f;l) |
| THM | filter_map | 'b,'a:S. f1:'b  . f2:'a  'b. l:'a List.
filter(f1;map(f2;l)) = map(f2;filter(f1 o f2;l)) |
| THM | length_seg | 'a:S. n,k: . l:'a List. n + k ||l||  ||seg(n;k;l)|| = n |
| THM | append_nil | 'a:S. ( l:'a List. l @ [] = l) ( l:'a List. l = l) |
| THM | append_snoc | 'a:S. l1:'a List. x:'a. l2:'a List.
l1 @ snoc(x;l2) = snoc(x;l1 @ l2) |
| THM | reverse_append_2 | 'a:S. l1,l2:'a List. rev(l2) @ rev(l1) = rev(l2) @ rev(l1) |
| THM | append_foldr | 'a:S. l1,l2:'a List. l1 @ l2 = foldr( x:'a. l:'a List. x::l;l2;l1) |
| THM | append_foldl | 'a:S. l1,l2:'a List.
l1 @ l2 = foldl( l':'a List. x:'a. snoc(x;l');l1;l2) |
| THM | foldr_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) |
| THM | foldl_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) |
| THM | cons_append | 'a:S. x:'a. l:'a List. (x::l) = (x::l) |
| THM | assoc_append | 'a:S. assoc('a List; l1:'a List. l2:'a List. l1 @ l2) |
| THM | monoid_append_nil | 'a:S. monoid('a List; l1:'a List. l2:'a List. l1 @ l2;[]) |
| THM | append_length_eq | 'a:S. l1,l1':'a List.
||l1|| = ||l1'||
 ( l2,l2':'a List.
||l2|| = ||l2'||
 (l1 @ l2 = l1' @ l2'   l1 = l1' l2 = l2')) |
| THM | filter_append | 'a:S. f:'a  . l1,l2:'a List.
filter(f;l1 @ l2) = filter(f;l1) @ filter(f;l2) |
| THM | flat_snoc | 'a:S. x:'a List. l:'a List List.
flatten(snoc(x;l)) = flatten(l) @ x |
| THM | flat_foldr | 'a:S. l:'a List List.
flatten(l) = foldr( l1:'a List. l2:'a List. l1 @ l2;[];l) |
| THM | flat_foldl | 'a:S. l:'a List List.
flatten(l) = foldl( l1:'a List. l2:'a List. l1 @ l2;[];l) |
| THM | length_flat | 'a:S. l:'a List List.
||flatten(l)|| = it_sum(map( l:'a List. ||l||;l)) |
| THM | reverse_foldr | 'a:S. l:'a List. rev(l) = foldr( x:'a. l:'a List. snoc(x;l);[];l) |
| THM | reverse_foldl | 'a:S. l:'a List. rev(l) = foldl( l':'a List. x:'a. x::l';[];l) |
| THM | length_reverse | 'a:S. l:'a List. ||rev(l)|| = ||l|| |
| THM | reverse_eq_nil | 'a:S. l:'a List. rev(l) = []   l = [] |
| THM | all_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) |
| THM | all_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) |
| THM | all_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) |
| THM | all_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) |
| THM | some_el_snoc | 'a:S. P:'a  . x:'a. l:'a List.
some(P;snoc(x;l))   (P x) some(P;l) |
| THM | not_all_el_some_el | 'a:S. P:'a  . l:'a List.  every(P;l) = some(( p: .  p) o P;l) |
| THM | not_some_el_all_el | 'a:S. P:'a  . l:'a List.  some(P;l) = every(( p: .  p) o P;l) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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) |
| THM | is_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) |
| THM | is_el_snoc | 'a:S. eq:eq('a). y,x:'a. l:'a List.
y _{eq} snoc(x;l) = (y = x)  (y _{eq} l) |
| THM | sum_snoc | x: . l: List. it_sum(snoc(x;l)) = it_sum(l) + x |
| THM | sum_foldr | l: List. it_sum(l) = foldr( m: . n: . m + n;0;l) |
| THM | sum_foldl | l: List. it_sum(l) = foldl( m: . n: . m + n;0;l) |
| THM | is_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) |
| THM | is_prefix_append | 'a:S. eq:eq('a). l1,l2:'a List.
is_prefix(eq;l1;l2)   ( l:'a List. l1 = l2 @ l) |
| THM | is_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) |
| THM | is_suffix_append | 'a:S. eq:eq('a). l1,l2:'a List.
is_suffix(eq;l1;l2)   ( l:'a List. l1 = l @ l2) |
| THM | is_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') |
| THM | is_sublist_append | 'a:S. eq:eq('a). l1,l2:'a List.
is_sublist(eq;l1;l2)   ( l,l':'a List. l1 = l @ l2 @ l') |
| THM | is_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) |
| THM | is_prefix_is_sublist | 'a:S. eq:eq('a). l1,l2:'a List.
is_prefix(eq;l1;l2)  is_sublist(eq;l1;l2) |
| THM | is_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) |
| THM | is_suffix_is_sublist | 'a:S. eq:eq('a). l1,l2:'a List.
is_suffix(eq;l1;l2)  is_sublist(eq;l1;l2) |
| THM | is_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) |
| THM | is_prefix_reverse__old1 | 'a:S. eq:eq('a). l1,l2:'a List.
is_prefix(eq;rev(l1);rev(l2))   is_suffix(eq;l1;l2) |
| THM | is_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) |
| THM | is_prefix_reverse | 'a:S. eq:eq('a). l1,l2:'a List.
is_prefix(eq;rev(l1);rev(l2)) = is_suffix(eq;l1;l2) |
| THM | is_suffix_reverse__old1 | 'a:S. eq:eq('a). l2,l1:'a List.
is_suffix(eq;rev(l1);rev(l2))   is_prefix(eq;l1;l2) |
| THM | is_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) |
| THM | is_suffix_reverse | 'a:S. eq:eq('a). l2,l1:'a List.
is_suffix(eq;rev(l1);rev(l2)) = is_prefix(eq;l1;l2) |
| THM | is_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) |
| THM | is_sublist_reverse | 'a:S. eq:eq('a). l1,l2:'a List.
is_sublist(eq;rev(l1);rev(l2)) = is_sublist(eq;l1;l2) |
| THM | prefix_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) |
| THM | prefix_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 ) |
| THM | is_prefix_prefix__old | 'a:S. P:'a  . l:'a List.
is_prefix(<eq_pred:( x:'a. y:'a. x = y)>l;prefix(P;l)) |
| THM | is_prefix_prefix | 'a:S. eq:eq('a). P:'a  . l:'a List.
is_prefix(eq;l;prefix(P;l)) |
| THM | length_scanl | 'b,'a:S. f:'b  'a  'b. e:'b. l:'a List.
||scanl(f;e;l)|| = ||l|| + 1 |
| THM | length_scanr | 'b,'a:S. f:'a  'b  'b. e:'b. l:'a List.
||scanr(f;e;l)|| = ||l|| + 1 |
| THM | comm_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))) |
| THM | comm_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))) |
| THM | fcomm_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))) |
| THM | fcomm_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))) |
| THM | foldl_single | 'a,'b:S. f:'a  'b  'a. e:'a. x:'b. f e x = f e x |
| THM | foldr_single | 'b,'a:S. f:'a  'b  'b. e:'b. x:'a. f x e = f x e |
| THM | foldr_cons_nil | 'a:S. l:'a List. foldr( x:'a. l:'a List. x::l;[];l) = l |
| THM | foldl_snoc_nil | 'a:S. l:'a List. foldl( xs:'a List. x:'a. snoc(x;xs);[];l) = l |
| THM | foldr_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)) |
| THM | foldl_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)) |
| THM | foldr_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) |
| THM | foldl_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) |
| THM | foldr_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) |
| THM | foldl_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) |
| THM | all_el_foldr | 'a:S. P:'a  . l:'a List.
every(P;l) = foldr( x:'a. l': . P x  l';tt;l) |
| THM | all_el_foldl | 'a:S. P:'a  . l:'a List.
every(P;l) = foldl( l': . x:'a. l'  P x;tt;l) |
| THM | some_el_foldr | 'a:S. P:'a  . l:'a List.
some(P;l) = foldr( x:'a. l': . (P x)  l';ff;l) |
| THM | some_el_foldl | 'a:S. P:'a  . l:'a List.
some(P;l) = foldl( l': . x:'a. l'  (P x);ff;l) |
| THM | all_el_foldr_map | 'a:S. P:'a  . l:'a List.
every(P;l) = foldr( p: . q: . p  q;tt;map(P;l)) |
| THM | all_el_foldl_map | 'a:S. P:'a  . l:'a List.
every(P;l) = foldl( p: . q: . p  q;tt;map(P;l)) |
| THM | some_el_foldr_map | 'a:S. P:'a  . l:'a List.
some(P;l) = foldr( p: . q: . p  q;ff;map(P;l)) |
| THM | some_el_foldl_map | 'a:S. P:'a  . l:'a List.
some(P;l) = foldl( p: . q: . p  q;ff;map(P;l)) |
| THM | foldr_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) |
| THM | foldl_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) |
| THM | assoc_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)))) |
| THM | assoc_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)))) |
| THM | map_flat | 'a,'b:S. f:'a  'b. l:'a List List.
map(f;flatten(l)) = flatten(map( l:'a List. map(f;l);l)) |
| THM | filter_flat | 'a:S. P:'a  . l:'a List List.
filter(P;flatten(l)) = flatten(map( l:'a List. filter(P;l);l)) |
| THM | some_el_map | 'b,'a:S. P:'b  . f:'a  'b. l:'a List.
some(P;map(f;l)) = some(P o f;l) |
| THM | some_el_append | 'a:S. P:'a  . l1,l2:'a List.
some(P;l1 @ l2) = some(P;l1)  some(P;l2) |
| THM | some_el_disj | 'a:S. P,Q:'a  . l:'a List.
some( x:'a. (P x)  (Q x);l) = some(P;l)  some(Q;l) |
| THM | is_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) |
| THM | is_el_append | 'a:S. eq:eq('a). l1,l2:'a List. x:'a.
(x _{eq} l1 @ l2)   (x _{eq} l1) (x _{eq} l2) |
| THM | is_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) |
| THM | is_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) |
| THM | is_el_foldr | 'a:S. eq:eq('a). y:'a. l:'a List.
y _{eq} l = foldr( x:'a. l': . (y = x)  l';ff;l) |
| THM | is_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) |
| THM | is_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) |
| THM | is_el_foldl | 'a:S. eq:eq('a). y:'a. l:'a List.
y _{eq} l = foldl( l': . x:'a. l'  (y = x);ff;l) |
| THM | null_foldr | 'a:S. l:'a List. mt(l)   foldr( x:'a. l': . ff;tt;l) |
| THM | null_foldl | 'a:S. l:'a List. mt(l)   foldl( x: . l':'a. ff;tt;l) |
| THM | map_reverse | 'a,'b:S. f:'a  'b. l:'a List. map(f;rev(l)) = rev(map(f;l)) |
| THM | filter_reverse | 'a:S. P:'a  . l:'a List. filter(P;rev(l)) = rev(filter(P;l)) |
| THM | last_char | 'a:S. x:'a. l:'a List. last_el(snoc(x;l)) = x |
| THM | butlast_char | 'a:S. x:'a. l:'a List. but_last_el(snoc(x;l)) = l |
| THM | seg_length_id | 'a:S. l:'a List. seg(||l||;0;l) = l |
| THM | seg_suc_cons | 'a:S. m,n: . l:'a List. x:'a. seg(m;n + 1;x::l) = seg(m;n;l) |
| THM | seg_0_snoc | 'a:S. m: . l:'a List. x:'a.
m ||l||  seg(m;0;snoc(x;l)) = seg(m;0;l) |
| THM | butlastn_seg | 'a:S. n: . l:'a List.
n ||l||  butlastn(n;l) = seg(nnsub(||l||;n);0;l) |
| THM | lastn_cons | 'a:S. n: . l:'a List.
n ||l||  ( x:'a. lastn(n;x::l) = lastn(n;l)) |
| THM | length_lastn | 'a:S. n: . l:'a List. n ||l||  ||lastn(n;l)|| = n |
| THM | lastn_length_id | 'a:S. l:'a List. lastn(||l||;l) = l |
| THM | lastn_lastn | 'a:S. l:'a List. n,m: .
m ||l||  n m  lastn(n;lastn(m;l)) = lastn(n;l) |
| THM | firstn_length_id | 'a:S. l:'a List. firstn(||l||;l) = l |
| THM | firstn_snoc | 'a:S. n: . l:'a List.
n ||l||  ( x:'a. firstn(n;snoc(x;l)) = firstn(n;l)) |
| THM | butlastn_length_nil | 'a:S. l:'a List. butlastn(||l||;l) = [] |
| THM | butlastn_suc_butlast | 'a:S. n: . l:'a List.
n < ||l||  butlastn(n + 1;l) = butlastn(n;but_last_el(l)) |
| THM | butlastn_butlast | 'a:S. n: . l:'a List.
n < ||l||  butlastn(n;but_last_el(l)) = but_last_el(butlastn(n;l)) |
| THM | length_butlastn | 'a:S. n: . l:'a List.
n ||l||  ||butlastn(n;l)|| = nnsub(||l||;n) |
| THM | butlastn_butlastn | 'a:S. m,n: . l:'a List.
n + m ||l||  butlastn(n;butlastn(m;l)) = butlastn(n + m;l) |
| THM | append_butlastn_lastn | 'a:S. n: . l:'a List. n ||l||  butlastn(n;l) @ lastn(n;l) = l |
| THM | append_firstn_lastn | 'a:S. m,n: . l:'a List.
m + n = ||l||  firstn(n;l) @ lastn(m;l) = l |
| THM | butlastn_append2 | 'a:S. n: . l1,l2:'a List.
n ||l2||  butlastn(n;l1 @ l2) = l1 @ butlastn(n;l2) |
| THM | butlastn_length_append | 'a:S. l2,l1:'a List. butlastn(||l2||;l1 @ l2) = l1 |
| THM | lastn_length_append | 'a:S. l2,l1:'a List. lastn(||l2||;l1 @ l2) = l2 |
| THM | butlastn_cons | 'a:S. n: . l:'a List.
n ||l||  ( x:'a. butlastn(n;x::l) = (x::butlastn(n;l))) |
| THM | butlastn_length_cons | 'a:S. l:'a List. x:'a. butlastn(||l||;x::l) = (x::[]) |
| THM | last_lastn_last | 'a:S. n: . l:'a List.
n ||l||  0 < n  last_el(lastn(n;l)) = last_el(l) |
| THM | butlastn_lastn_nil | 'a:S. n: . l:'a List. n ||l||  butlastn(n;lastn(n;l)) = [] |
| THM | lastn_butlastn | 'a:S. n,m: . l:'a List.
n + m ||l||  lastn(n;butlastn(m;l)) = butlastn(m;lastn(n + m;l)) |
| THM | butlastn_lastn | 'a:S. m,n: . l:'a List.
m n n ||l||
 butlastn(m;lastn(n;l)) = lastn(nnsub(n;m);butlastn(m;l)) |
| THM | lastn_1 | 'a:S. l:'a List. (l = [])  lastn(1;l) = (last_el(l)::[]) |
| THM | butlastn_1 | 'a:S. l:'a List. (l = [])  butlastn(1;l) = but_last_el(l) |
| THM | butlastn_append1 | 'a:S. l2:'a List. n: .
||l2|| n
 ( l1:'a List. butlastn(n;l1 @ l2) = butlastn(nnsub(n;||l2||);l1)) |
| THM | lastn_append2 | 'a:S. n: . l2:'a List.
n ||l2||  ( l1:'a List. lastn(n;l1 @ l2) = lastn(n;l2)) |
| THM | lastn_append1 | 'a:S. l2:'a List. n: .
||l2|| n
 ( l1:'a List. lastn(n;l1 @ l2) = lastn(nnsub(n;||l2||);l1) @ l2) |
| THM | lastn_map | 'b,'a:S. n: . l:'a List.
n ||l||  ( f:'a  'b. lastn(n;map(f;l)) = map(f;lastn(n;l))) |
| THM | butlastn_map | 'b,'a:S. n: . l:'a List.
n ||l||
 ( f:'a  'b. butlastn(n;map(f;l)) = map(f;butlastn(n;l))) |
| THM | all_el_lastn | 'a:S. P:'a  . l:'a List.
every(P;l)  ( m: . m ||l||  every(P;lastn(m;l))) |
| THM | all_el_butlastn | 'a:S. P:'a  . l:'a List.
every(P;l)  ( m: . m ||l||  every(P;butlastn(m;l))) |
| THM | length_firstn_2 | 'a:S. n: . l:'a List. n ||l||  ||firstn(n;l)|| = n |
| THM | firstn_firstn | 'a:S. m: . l:'a List.
m ||l||  ( n: . n m  firstn(n;firstn(m;l)) = firstn(n;l)) |
| THM | length_butfirstn | 'a:S. n: . l:'a List.
n ||l||  ||nth_tl(n;l)|| = nnsub(||l||;n) |
| THM | butfirstn_length_nil | 'a:S. l:'a List. nth_tl(||l||;l) = [] |
| THM | butfirstn_append1 | 'a:S. n: . l1:'a List.
n ||l1||  ( l2:'a List. nth_tl(n;l1 @ l2) = nth_tl(n;l1) @ l2) |
| THM | butfirstn_append2 | 'a:S. l1:'a List. n: .
||l1|| n
 ( l2:'a List. nth_tl(n;l1 @ l2) = nth_tl(nnsub(n;||l1||);l2)) |
| THM | butfirstn_butfirstn | 'a:S. n,m: . l:'a List.
n + m ||l||  nth_tl(n;nth_tl(m;l)) = nth_tl(n + m;l) |
| THM | append_firstn_butfirstn | 'a:S. n: . l:'a List. n ||l||  firstn(n;l) @ nth_tl(n;l) = l |
| THM | lastn_seg | 'a:S. n: . l:'a List.
n ||l||  lastn(n;l) = seg(n;nnsub(||l||;n);l) |
| THM | firstn_seg | 'a:S. n: . l:'a List. n ||l||  firstn(n;l) = seg(n;0;l) |
| THM | butfirstn_seg | 'a:S. n: . l:'a List.
n ||l||  nth_tl(n;l) = seg(nnsub(||l||;n);n;l) |
| THM | append_butlast_last | 'a:S. l:'a List. (l = [])  but_last_el(l) @ (last_el(l)::[]) = l |
| THM | butfirstn_snoc | 'a:S. n: . l:'a List.
n ||l||  ( x:'a. nth_tl(n;snoc(x;l)) = snoc(x;nth_tl(n;l))) |
| THM | append_butlastn_butfirstn | 'a:S. m,n: . l:'a List.
m + n = ||l||  butlastn(m;l) @ nth_tl(n;l) = l |
| THM | seg_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) |
| THM | seg_append1 | 'a:S. n,m: . l1:'a List.
n + m ||l1||  ( l2:'a List. seg(n;m;l1 @ l2) = seg(n;m;l1)) |
| THM | seg_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) |
| THM | seg_firstn_butfistn | 'a:S. n,m: . l:'a List.
n + m ||l||  seg(n;m;l) = firstn(n;nth_tl(m;l)) |
| THM | seg_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) |
| THM | seg_length_snoc | 'a:S. l:'a List. x:'a. seg(1;||l||;snoc(x;l)) = (x::[]) |
| THM | seg_snoc | 'a:S. n,m: . l:'a List.
n + m ||l||  ( x:'a. seg(n;m;snoc(x;l)) = seg(n;m;l)) |
| THM | ell_seg | 'a:S. n: . l:'a List.
n < ||l||  ell(n;l) = head(seg(1;nnsub(||l||;n) - 1;l)) |
| THM | snoc_foldr | 'a:S. x:'a. l:'a List.
snoc(x;l) = foldr( x:'a. l:'a List. x::l;x::[];l) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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)) |
| THM | filter_filter | 'a:S. P,Q:'a  . l:'a List.
filter(P;filter(Q;l)) = filter( x:'a. P x  Q x;l) |
| THM | fcomm_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)))) |
| THM | fcomm_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)))) |
| THM | foldr_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))) |
| THM | foldr_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))) |
| THM | comm_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)) |
| THM | comm_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)) |
| THM | ell_last | 'a:S. l:'a List. mt(l)  ell 0 l = last l |
| THM | ell_0_snoc | 'a:S. l:'a List. x:'a. ell(0;snoc(x;l)) = x |
| THM | ell_cons | 'a:S. n: . l:'a List. n < ||l||  ( x:'a. ell(n;x::l) = ell(n;l)) |
| THM | ell_length_cons | 'a:S. l:'a List. x:'a. ell(||l||;x::l) = x |
| THM | ell_length_snoc | 'a:S. l:'a List. x:'a.
ell(||l||;snoc(x;l)) = if null(l) then x else head(l) fi |
| THM | ell_append2 | 'a:S. n: . l2:'a List.
n < ||l2||  ( l1:'a List. ell(n;l1 @ l2) = ell(n;l2)) |
| THM | ell_pre_length | 'a:S. l:'a List. (l = [])  ell(||l|| - 1;l) = head(l) |
| THM | el_length_snoc | 'a:S. l:'a List. x:'a. snoc(x;l)[||l||] = x |
| THM | el_pre_length | 'a:S. l:'a List. (l = [])  l[(||l|| - 1)] = last_el(l) |
| THM | el_snoc | 'a:S. n: . l:'a List. n < ||l||  ( x:'a. snoc(x;l)[n] = l[n]) |
| THM | el_ell | 'a:S. n: . l:'a List.
n < ||l||  l[n] = ell(nnsub(||l||;n) - 1;l) |
| THM | el_length_append | 'a:S. l2,l1:'a List. mt(l2)  el ||l1|| (l1 @ l2) = hd l2 |
| THM | ell_el | 'a:S. n: . l:'a List.
n < ||l||  ell(n;l) = l[(nnsub(||l||;n) - 1)] |
| THM | ell_map | 'b,'a:S. n: . l:'a List. f:'a  'b.
n < ||l||  ell(n;map(f;l)) = f ell(n;l) |
| THM | length_butlast | 'a:S. l:'a List. (l = [])  ||but_last_el(l)|| = ||l|| - 1 |
| THM | butfirstn_length_append | 'a:S. l1,l2:'a List. nth_tl(||l1||;l1 @ l2) = l2 |
| THM | firstn_append1 | 'a:S. n: . l1:'a List.
n ||l1||  ( l2:'a List. firstn(n;l1 @ l2) = firstn(n;l1)) |
| THM | firstn_append2 | 'a:S. l1:'a List. n: .
||l1|| n
 ( l2:'a List
firstn(n;l1 @ l2) = l1 @ firstn(nnsub(n;||l1||);l2)) |
| THM | firstn_length_append | 'a:S. l1,l2:'a List. firstn(||l1||;l1 @ l2) = l1 |
| THM | reverse_flat | 'a:S. l:'a List List.
rev(flatten(l)) = flatten(rev(map( l:'a List. rev(l);l))) |
| THM | map_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)) |
| THM | map_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)) |
| THM | flat_append | 'a:S. l1,l2:'a List List.
flatten(l1 @ l2) = flatten(l1) @ flatten(l2) |
| THM | flat_reverse | 'a:S. l:'a List List.
flatten(rev(l)) = rev(flatten(map( l:'a List. rev(l);l))) |
| THM | flat_flat | 'a:S. l:'a List List List.
flatten(flatten(l)) = flatten(map( l:'a List List. flatten(l);l)) |
| THM | all_el_reverse | 'a:S. P:'a  . l:'a List. every(P;rev(l)) = every(P;l) |
| THM | some_el_reverse__old | 'a:S. P:'a  . l:'a List. some(P;rev(l))   some(P;l) |
| THM | some_el_reverse | 'a:S. P:'a  . l:'a List. some(P;rev(l)) = some(P;l) |
| THM | all_el_seg | 'a:S. P:'a  . l:'a List.
every(P;l)  ( m,k: . m + k ||l||  every(P;seg(m;k;l))) |
| THM | all_el_firstn | 'a:S. P:'a  . l:'a List.
every(P;l)  ( m: . m ||l||  every(P;firstn(m;l))) |
| THM | all_el_butfirstn | 'a:S. P:'a  . l:'a List.
every(P;l)  ( m: . m ||l||  every(P;nth_tl(m;l))) |
| THM | some_el_seg | 'a:S. m,k: . l:'a List.
m + k ||l||  ( P:'a  . some(P;seg(m;k;l))  some(P;l)) |
| THM | some_el_firstn | 'a:S. m: . l:'a List.
m ||l||  ( P:'a  . some(P;firstn(m;l))  some(P;l)) |
| THM | some_el_butfirstn | 'a:S. m: . l:'a List.
m ||l||  ( P:'a  . some(P;nth_tl(m;l))  some(P;l)) |
| THM | some_el_lastn | 'a:S. m: . l:'a List.
m ||l||  ( P:'a  . some(P;lastn(m;l))  some(P;l)) |
| THM | some_el_butlastn | 'a:S. m: . l:'a List.
m ||l||  ( P:'a  . some(P;butlastn(m;l))  some(P;l)) |
| THM | is_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) |
| THM | is_el_reverse__old1 | 'a:S. eq:eq('a). x:'a. l:'a List.
(x _{eq} rev(l))   (x _{eq} l) |
| THM | is_el_reverse | 'a:S. eq:eq('a). x:'a. l:'a List. x _{eq} rev(l) = x _{eq} l |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_el_filter | 'a:S. eq:eq('a). P:'a  . x:'a.
(P x)  ( l:'a List. x _{eq} filter(P;l) = x _{eq} l) |
| THM | is_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)) |
| THM | is_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)) |
| THM | is_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) |
| THM | is_el_some_el__old1 | 'a:S. eq:eq('a). x:'a. l:'a List.
(x _{eq} l)   some( y:'a. x = y;l) |
| THM | is_el_some_el | 'a:S. eq:eq('a). x:'a. l:'a List.
x _{eq} l = some( y:'a. x = y;l) |
| THM | is_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)) |
| THM | is_el_firstn | 'a:S. eq:eq('a). m: . l:'a List.
m ||l||  ( x:'a. (x _{eq} firstn(m;l))  (x _{eq} l)) |
| THM | is_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)) |
| THM | is_el_butfirstn | 'a:S. eq:eq('a). m: . l:'a List.
m ||l||  ( x:'a. (x _{eq} nth_tl(m;l))  (x _{eq} l)) |
| THM | is_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)) |
| THM | is_el_butlastn | 'a:S. eq:eq('a). m: . l:'a List.
m ||l||  ( x:'a. (x _{eq} butlastn(m;l))  (x _{eq} l)) |
| THM | is_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)) |
| THM | is_el_lastn | 'a:S. eq:eq('a). m: . l:'a List.
m ||l||  ( x:'a. (x _{eq} lastn(m;l))  (x _{eq} l)) |
| THM | zip_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))) |
| THM | unzip_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)> |
| THM | length_zip | 'a,'b:S. l1:'a List. l2:'b List.
||l1|| = ||l2||  ||zip(l1;l2)|| = ||l1|| ||zip(l1;l2)|| = ||l2|| |
| THM | length_unzip_fst | 'a,'b:S. l:('a 'b) List. ||unzip_fst(l)|| = ||l|| |
| THM | length_unzip_snd | 'a,'b:S. l:('a 'b) List. ||unzip_snd(l)|| = ||l|| |
| THM | zip_unzip | 'a,'b:S. l:('a 'b) List. let <l,l'> = unzip(l) in zip(l;l') = l |
| THM | unzip_zip | 'a,'b:S. l1:'a List. l2:'b List.
||l1|| = ||l2||  unzip(zip(l1;l2)) = <l1, l2> |
| THM | sum_append | l1,l2: List. it_sum(l1 @ l2) = it_sum(l1) + it_sum(l2) |
| THM | sum_reverse | l: List. it_sum(rev(l)) = it_sum(l) |
| THM | sum_flat | l: List List
it_sum(flatten(l)) = it_sum(map( l: List. it_sum(l);l)) |
| THM | el_append1 | 'a:S. n: . l1,l2:'a List. n < ||l1||  (l1 @ l2)[n] = l1[n] |
| THM | el_map | 'b,'a:S. n: . l:'a List.
n < ||l||  ( f:'a  'b. map(f;l)[n] = f l[n]) |
| THM | el_seg | 'a:S. n: . l:'a List. n < ||l||  l[n] = head(seg(1;n;l)) |
| THM | el_is_el__old | 'a:S. n: . l:'a List.
n < ||l||  (l[n] _{<eq_pred:( x:'a. y:'a. x = y)>} l) |
| THM | el_is_el | 'a:S. eq:eq('a). n: . l:'a List. n < ||l||  (l[n] _{eq} l) |
| THM | tl_snoc | 'a:S. x:'a. l:'a List.
tl(snoc(x;l)) = if null(l) then [] else snoc(x;tl(l)) fi |
| THM | el_reverse | 'a:S. n: . l:'a List.
n < ||l||  rev(l)[n] = l[(nnsub(||l||;n) - 1)] |
| THM | el_reverse_ell | 'a:S. n: . l:'a List. n < ||l||  rev(l)[n] = ell(n;l) |
| THM | ell_length_append | 'a:S. l1,l2:'a List. mt(l1)  ell ||l2|| (l1 @ l2) = last l1 |
| THM | ell_is_el__old | 'a:S. n: . l:'a List.
n < ||l||  (l[n] _{<eq_pred:( x:'a. y:'a. x = y)>} l) |
| THM | ell_is_el | 'a:S. eq:eq('a). n: . l:'a List. n < ||l||  (l[n] _{eq} l) |
| THM | ell_reverse | 'a:S. n: . l:'a List.
n < ||l||  ell(n;rev(l)) = ell(nnsub(||l||;n) - 1;l) |
| THM | ell_reverse_el | 'a:S. n: . l:'a List. n < ||l||  ell(n;rev(l)) = l[n] |
| THM | firstn_butlastn | 'a:S. n: . l:'a List.
n ||l||  firstn(n;l) = butlastn(nnsub(||l||;n);l) |
| THM | butlastn_firstn | 'a:S. n: . l:'a List.
n ||l||  butlastn(n;l) = firstn(nnsub(||l||;n);l) |
| THM | lastn_butfirstn | 'a:S. n: . l:'a List.
n ||l||  lastn(n;l) = nth_tl(nnsub(||l||;n);l) |
| THM | butfirstn_lastn | 'a:S. n: . l:'a List.
n ||l||  nth_tl(n;l) = lastn(nnsub(||l||;n);l) |
| THM | seg_lastn_butlastn | 'a:S. n,m: . l:'a List.
n + m ||l||
 seg(n;m;l) = lastn(n;butlastn(nnsub(||l||;n + m);l)) |
| THM | butfirstn_reverse | 'a:S. n: . l:'a List.
n ||l||  nth_tl(n;rev(l)) = rev(butlastn(n;l)) |
| THM | butlastn_reverse | 'a:S. n: . l:'a List.
n ||l||  butlastn(n;rev(l)) = rev(nth_tl(n;l)) |
| THM | lastn_reverse | 'a:S. n: . l:'a List.
n ||l||  lastn(n;rev(l)) = rev(firstn(n;l)) |
| THM | firstn_reverse | 'a:S. n: . l:'a List.
n ||l||  firstn(n;rev(l)) = rev(lastn(n;l)) |
| THM | seg_reverse | 'a:S. n,m: . l:'a List.
n + m ||l||  seg(n;m;rev(l)) = rev(seg(n;nnsub(||l||;n + m);l)) |
| THM | length_genlist | 'a:S. f:  'a. n: . ||rev(genlist(f;n))|| = n |
| THM | length_replicate | 'a:S. n: . x:'a. ||replicate(n;x)|| = n |
| THM | is_el_replicate__old | 'a:S. n: .
0 < n
 ( x:'a. (x _{<eq_pred:( x:'a. y:'a. x = y)>} replicate(n;x))) |
| THM | is_el_replicate__old1 | 'a:S. n: .
0 < n
 ( x:'a. (x _{<eq_pred:( x:'a. y:'a. x = y)>} replicate(n;x))) |
| THM | is_el_replicate | 'a:S. eq:eq('a). n: . 0 < n  ( x:'a. (x _{eq} replicate(n;x))) |
| THM | all_el_replicate | 'a:S. x:'a. n: . every( y:'a. x = y;replicate(n;x)) |
| THM | and_el_foldl | l: List. and_el(l) = foldl( p: . q: . p  q;tt;l) |
| THM | and_el_foldr__old | l: List. and_el(l)   foldr( p: . q: . p  q;tt;l) |
| THM | and_el_foldr | l: List. and_el(l) = foldr( p: . q: . p  q;tt;l) |
| THM | or_el_foldl__old | l: List. or_el(l)   foldl( p: . q: . p  q;ff;l) |
| THM | or_el_foldl | l: List. or_el(l) = foldl( p: . q: . p  q;ff;l) |
| THM | or_el_foldr__old | l: List. or_el(l)   foldr( p: . q: . p  q;ff;l) |
| THM | or_el_foldr | l: List. or_el(l) = foldr( p: . q: . p  q;ff;l) |
| THM | map2_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))) |
| THM | ell_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))) |
| THM | el_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]) |
| THM | ell_snoc | 'a:S. n: . x:'a. l:'a List.
0 < n n - 1 < ||l||  ell(n;snoc(x;l)) = ell(n - 1;l) |
| THM | ell_suc_snoc | 'a:S. n: . x:'a. l:'a List.
n < ||l||  ell(n + 1;snoc(x;l)) = ell(n;l) |
| THM | ell_append1 | 'a:S. l2:'a List. n: .
||l2|| n n < ||l2||
 ( l1:'a List. ell(n;l1 @ l2) = ell(nnsub(n;||l2||);l1)) |
| THM | el_append2 | 'a:S. l1:'a List. n: .
||l1|| n
 ( l2:'a List
n < ||l1|| + ||l2||  (l1 @ l2)[n] = l2[nnsub(n;||l1||)]) |
| THM | el_cons | 'a:S. n: .
0 < n  ( x:'a. l:'a List. n ||l||  (x::l)[n] = l[(n - 1)]) |
| COM | List_additional_theorems | -------------- |
| ML | cancel_assert_of_every_simp | delete_simp (OLD_id_to_simp_table_lookup' `assert_of_every`) ;; |
| ML | replaced_hol_type_inf_hack | add_get_type_top_level_hook `hol_type_inf_hack` (\T. hol_to_nuprl T) ;
; |
| ML | lift_assert_simpset | map (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``
;; |
| THM | nil_if_mt | A: . l:A List. mt(l)  l = [] |
| THM | map_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)) |
| THM | all_el_snoc_2 | 'a:S. P:'a  . x:'a. l:'a List.
every(P;snoc(x;l))   every(P;l) (P x) |
| THM | all_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) |
| THM | all_el_map_2 | 'b,'a:S. P:'b  . f:'a  'b. l:'a List.
every(P;map(f;l)) = every(P o f;l) |
| THM | all_el_append_2 | 'a:S. P:'a  . l1,l2:'a List.
every(P;l1 @ l2) = every(P;l1)  every(P;l2) |
| THM | some_el_snoc_2 | 'a:S. P:'a  . x:'a. l:'a List.
some(P;snoc(x;l)) = (P x)  some(P;l) |
| THM | some_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) |
| THM | length_unzip_fst_2 | 'a,'b:S. l:('a 'b) List. ||unzip(l).1|| = ||l|| |
| THM | length_unzip_snd_2 | 'a,'b:S. l:('a 'b) List. ||unzip(l).2|| = ||l|| |
| THM | zip_unzip_2 | 'a,'b:S. l:('a 'b) List. zip(unzip(l).1;unzip(l).2) = l |
| ML | List_simpset | simpset_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 ;; |
| ML | List_add_to_unfold_simp | map (add_to_simpset `unfold` o C lemma_to_cond_simp [DefaultSimpCondit
ion])
``nil_if_mt cons_wd_2``
;; |
| ML | copy_simps_from_OLD_table | copy_simps_from_OLD_table() ;; |
| ML | HOL_standard_lib_simps | simpset_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;; |
| THM | length_induction | 'a:S. P:'a List   .
( l:'a List. ( q:'a List. ||q|| < ||l||  P[q])  P[l])
 { l:'a List. P[l]} |
| THM | snoc_cases_2 | 'a:S. l:'a List. mt(l) ( x:'a. q:'a List. l = snoc(x;q)) |
| THM | snoc_induction | 'a:S. P:'a List   .
P[[]]
 ( x:'a. l:'a List. P[l]  P[snoc(x;l)])
 ( l:'a List. P[l]) |
| ML | mt_EqCD | update_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`
)
;; |