How to rewrite term in type signature for proof in Idris? -


basically, want prove either n - m or m - n equal 0 in recursive arithmetic. accomplish have been trying use rewrite ... in ... pattern without sucess.

the following base code:

data natural = c | s natural  resta : natural -> natural -> natural resta     c     = resta c     b     = c resta (s a) (s b) = resta b  data algunoescero : (n, m : natural) -> type   izquierdoescero : algunoescero c m   derechoescero :   algunoescero n c  alguna_resta_es_cero : (n, m: natural) -> algunoescero (resta n m) (resta m n) alguna_resta_es_cero c     m     = ?hoyo1 alguna_resta_es_cero n     c     = ?hoyo2 alguna_resta_es_cero (s n) (s m) = ?hoyo3

however, when inspecting first 2 holes

- + main.hoyo1 [p]  `--           m : natural      -----------------------------------------       main.hoyo1 : algunoescero (resta c m) m  - + main.hoyo2 [p]  `--           n : natural      -----------------------------------------       main.hoyo2 : algunoescero n (resta c n)

the way have been able move forward lemma in data algunoescero; way forward have read rewrite type using theorem like

cero_menos_algo_es_cero : (m: natural) -> resta c m = c cero_menos_algo_es_cero c     = refl cero_menos_algo_es_cero (s m) = refl

so easy point out of 2 minus going 0 , build datatype rewrite cero_menos_algo_es_cero in izquierdoescero. spits out:

when checking right hand side of alguna_resta_es_cero expected type              algunoescero (resta c m) (resta m c)       _ not have equality type ((m1 : natural) -> resta c m1 = c)

any resource pointers appreciated. (haven't been able find points in type driven development nor on documentation; maybe misunderstanding rewrite / proofs in general)

you need pattern-match 1 more time finish proof:

alguna_resta_es_cero : (n, m: natural) -> algunoescero (resta n m) (resta m n) alguna_resta_es_cero c c = izquierdoescero alguna_resta_es_cero c (s x) = izquierdoescero alguna_resta_es_cero (s x) c = derechoescero alguna_resta_es_cero (s x) (s y) = alguna_resta_es_cero x y

also, if defined subtraction function as

resta : natural -> natural -> natural resta c     b     = c resta     c     = resta (s a) (s b) = resta b

(notice pattern-match on first argument, opposed version starts pattern-matching on second one), proof of alguna_resta_es_cero mimic structure of function more closely:

alguna_resta_es_cero : (n, m: natural) -> algunoescero (resta n m) (resta m n) alguna_resta_es_cero c m = izquierdoescero alguna_resta_es_cero (s x) c = derechoescero alguna_resta_es_cero (s x) (s y) = alguna_resta_es_cero x y

Comments

Post a Comment

Popular posts from this blog

Sort a complex associative array in PHP -

this question has answer here: php sort array subarray value 5 answers i have associative array in php like: $newarray1 = array ( [producta] => array ( [link] => http://sanjosespartan.com/blog/products/agile-java-development/ [visitcount] => 4 ) [productd] => array ( [link] => http://sanjosespartan.com/blog/products/intro-to-go/ [visitcount] => 1 ) [productg] => array ( [link] => http://sanjosespartan.com/blog/products/node-js-for-developers/ [visitcount] => 1 ) [productb] => array ( [link] => http://sanjosespartan.com/blog/products/beginning-mysql/ [visitcount] => 1 ) [productc] => array ( [link] => http://sanjosespartan.com/blog/products/computer-networks/ [visitcount] => 1 ) ...
Read more

vb.net - How to ignore if a cell is empty nothing -

how use roscolor() ignore value (like empty cell) ? color row if value upper 5 when there nothing in cell, want ignore roscolor() apply, how? public sub roscolor() integer = 0 quotedatagridview1.rows.count() - 1 step +1 dim val integer val = quotedatagridview1.rows(i).cells(3).value if val = vbempty quotedatagridview1.rows(i).defaultcellstyle.backcolor = color.white elseif val < 5 quotedatagridview1.rows(i).defaultcellstyle.backcolor = color.red elseif val > 5 , val < 10 quotedatagridview1.rows(i).defaultcellstyle.backcolor = color.lightyellow end if next end sub you can check empty value following public sub roscolor() integer = 0 quotedatagridview1.rows.count() - 1 step +1 dim val = quotedatagridview1.rows(i).cells(3).value if isdbnull(val) or val nothing quotedatagridview1.rows(i).defaultcellstyle.backcolor = color.white ...
Read more

recursion - Can every recursive algorithm be improved with dynamic programming? -

i first year undergraduate csc student looking competitive programming. recursion involves defining , solving sub problems. understand, top down dynamic programming (dp) involves memoizing solutions sub problems reduce time complexity of algorithm. can top down dp used improve efficiency of every recursive algorithm overlapping sub problems? dp fail work , how can identify this? the short answer is: yes. however, there constraints. obvious 1 recursive calls must overlap. i.e. during execution of algorithm, recursive function must called multiple times same parameters. lets truncate recursion tree memoization. can use memoization reduce number of calls. however, reduction of calls comes price. need store results somewhere. next obvious constraint need have enough memory. comes not-so obvious constraint. memory access requires time. first need find result stored , maybe copy location. in cases, might faster let recursion calculate result instead of loading somewher...
Read more