[Nix-dev] Nix 1.2 released

[Shea Levy]

On 12/12/2012 01:12 PM, Florian Friesdorf wrote:
> Eelco Dolstra <eelco.dolstra at logicblox.com> 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.