On 12/12/2012 01:12 PM, Florian Friesdorf wrote: > Eelco Dolstra <[email protected]> writes: >> Hi, >> >> On 12/12/12 17:15, Shea Levy wrote: >> >>>>> The elem library function evaluates all list elements instead of >>>>> returning "true" after finding a matching element. >>>> Sure about that? This seems lazy enough: >>>> >>>> elem = >>>> builtins.elem or >>>> (x: list: fold (a: bs: x == a || bs) false list); >>>> >>> Shouldn't the bs come first? i.e. (a: bs: bs || x == a)? >> Not if you want to check from left to right. > Sorry, but I'm not getting it yet. What I understand: > > list = [0, 0, 1, 2, 3]; > x = 1; > > elem x list > > -> a: 3, x == a: false, bs: false > -> a: 2, x == a: false; bs: false > -> a: 1, x == a: true; bs: false > -> a: 0, x == a: false; bs: true > -> a: 0, x == a: false; bs: true > > Probably missing something very basic. > > For completeness sake, fold from lib/lists: > > fold = > if builtins ? elemAt > then op: nul: list: > let > len = length list; > fold' = n: > if n == len > then nul > else op (builtins.elemAt list n) (fold' (add n 1)); > in fold' 0 > else op: nul: > let fold' = list: > if list == [] > then nul > else op (head list) (fold' (tail list)); > in fold'; > > > The following would not evaluate all, I'd currently claim: > > elem' = x: list: if list == [] > then false > else head list == x || elem' x (tail list); >
Or, without using shorthands or shortcuts: elem x list -> (evaluate elem to a function) (x: list: fold (a: bs: x == a || bs) false list) x list -> (apply function to x) (list: fold (a: bs: x == a || bs) false list) list -> (apply function to list) fold (a: bs: x == a || bs) false list -> (evaluate fold to a function) (op: nul: list: if list == [] then nul else op (head list) (fold op nul (tail list))) (a: bs: x == a || bs) false list -> (apply function to a: bs: x == a || bs) (nul: list: if list == [] then nul else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) nul (tail list))) false list -> (apply function to false) (list: if list == [] then false else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) false (tail list))) list -> (apply function to list) if list == [] then false else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) false (tail list)) -> (evaluate list to a list) if [0 0 1 2 3] == [] then false else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) false (tail list)) -> (evaluate [0 0 1 2 3] == [] to a bool) if false then false else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) false (tail list)) -> (evaluate if false then x else y to y) (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) false (tail list)) -> (apply function to head list) (bs: x == (head list) || bs) (fold (a: bs: x == a || bs) false (tail list)) -> (apply function to fold (a: bs: x == a || bs) false (tail list)) x == (head list) || (fold (a: bs: x == a || bs) false (tail list)) -> (evaluate x to an integer) 1 == (head list) || (fold (a: bs: x == a || bs) false (tail list)) -> (memoized evaluate list to a list) 1 == (head [0 0 1 2 3]) || (fold (a: bs: x == a || bs) false (tail list)) -> (evaluate head [0 0 1 2 3] to an integer) 1 == 0 || (fold (a: bs: x == a || bs) false (tail list)) -> (evaluate 1 == 0 to a bool) false || (fold (a: bs: x == a || bs) false (tail list)) -> (evaluate false || x to x) fold (a: bs: 1 == a || bs) false (tail list) -> (memoized evaluate fold to a function) (op: nul: list: if list == [] then nul else op (head list) (fold op nul (tail list))) (a: bs: x == a || bs) false (tail list) -> (apply function to a: bs: x == a || bs) (nul: list: if list == [] then nul else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) nul (tail list))) false (tail list) -> (apply function to false) (list: if list == [] then false else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) false (tail list))) (tail list) -> (apply function to tail list) if (tail list) == [] then false else (a: bs: x == a || bs) (head (tail list)) (fold (a: bs: x == a || bs) false (tail (tail list))) -> (memoized evaluate list to a list) if (tail [0 0 1 2 3]) == [] then false else (a: bs: x == a || bs) (head (tail list)) (fold (a: bs: x == a || bs) false (tail (tail list))) -> (evaluate tail [0 0 1 2 3]) if [0 1 2 3] == [] then false else (a: bs: x == a || bs) (head (tail list)) (fold (a: bs: x == a || bs) false (tail (tail list))) -> (evaluate [0 1 2 3] == [] to a bool) if false then false else (a: bs: x == a || bs) (head (tail list)) (fold (a: bs: x == a || bs) false (tail (tail list))) -> (evaluate if false then x else y to y) (a: bs: x == a || bs) (head (tail list)) (fold (a: bs: x == a || bs) false (tail (tail list))) -> (apply function to head (tail list)) (bs: x == (head (tail list)) || bs) (fold (a: bs: x == a || bs) false (tail (tail list))) -> (apply function to fold (a: bs: x == a || bs) false (tail (tail list))) x == (head (tail list)) || (fold (a: bs: x == a || bs) false (tail (tail list))) -> (memoized evaluate x to an integer) 1 == (head (tail list)) || (fold (a: bs: x == a || bs) false (tail (tail list))) -> (memoized evaluate tail list to a list) 1 == (head [0 1 2 3]) || (fold (a: bs: x == a || bs) false (tail (tail list))) -> (evaluate head [0 1 2 3] to an integer) 1 == 0 || (fold (a: bs: x == a || bs) false (tail (tail list))) -> (evaluate 1 == 0 to a bool) false || (fold (a: bs: x == a || bs) false (tail (tail list))) -> (evaluate false || x to x) fold (a: bs: x == a || bs) false (tail (tail list)) -> (memozied evaluate fold to a function) (op: nul: list: if list == [] then nul else op (head list) (fold op nul (tail list))) (a: bs: x == a || bs) false (tail (tail list)) -> (apply function to a: bs: x == a || bs) (nul: list: if list == [] then nul else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) nul (tail list))) false (tail (tail list)) -> (apply function to false) (list: if list == [] then false else (a: bs: x == a || bs) (head list) (fold (a: bs: x == a || bs) false (tail list))) (tail (tail list)) -> (apply function to tail (tail list)) if (tail (tail list)) == [] then false else (a: bs: x == a || bs) (head (tail(tail list))) (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (memoized evaluate tail list to a list) if (tail [0 1 2 3]) == [] then false else (a: bs: x == a || bs) (head (tail(tail list))) (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (evaluate tail [0 1 2 3] to a list) if [1 2 3] == [] then false else (a: bs: x == a || bs) (head (tail(tail list))) (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (evaluate [1 2 3] == [] to a bool) if false then false else (a: bs: x == a || bs) (head (tail(tail list))) (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (evaluate if false then x else y to y) (a: bs: x == a || bs) (head (tail(tail list))) (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (apply function to head (tail(tail list))) (bs: x == (head (tail(tail list))) || bs) (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (apply function to fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) x == (head (tail(tail list))) || (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (memoized evaluate x to an integer) 1 == (head (tail(tail list))) || (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (memoized evaluate tail (tail list) to a list) 1 == (head [1 2 3]) || (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (evaluate head [1 2 3] to an integer) 1 == 1 || (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (evaluate 1 == 1 to a bool) true || (fold (a: bs: x == a || bs) false (tail ((tail) tail list)))) -> (evaluate true || x to true) true So 2 and 3 are never evaluated out of the list. _______________________________________________ nix-dev mailing list [email protected] http://lists.science.uu.nl/mailman/listinfo/nix-dev
