From 89375f7490377b396726b159f60ba4b914c85285 Mon Sep 17 00:00:00 2001 From: Igor Pashev Date: Fri, 17 Apr 2015 22:56:04 +0300 Subject: GCD via Nix expressions --- gcd.nix | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 gcd.nix diff --git a/gcd.nix b/gcd.nix new file mode 100644 index 0000000..385793c --- /dev/null +++ b/gcd.nix @@ -0,0 +1,40 @@ +/* + +See https://nixos.org/nix/ + +Usage: + +$ nix-instantiate --eval --expr "import ./gcd.nix [22 33 44 121]" +trace: gcd2: 44 <-> 121 +trace: gcd2: 121 <-> 44 +trace: gcd2: 44 <-> 33 +trace: gcd2: 33 <-> 11 +trace: gcd2: 11 <-> 0 +trace: gcd2: 33 <-> 11 +trace: gcd2: 11 <-> 0 +trace: gcd2: 22 <-> 11 +trace: gcd2: 11 <-> 0 +11 + +*/ + +list: + +let + inherit (builtins) div toString trace + tail head; + + rem = x: y: x - y*(div x y); + + gcd2 = x: y: trace "gcd2: ${toString x} <-> ${toString y}" + (if y == 0 then x else gcd2 y (rem x y)); + + gcd = nn: + let + x = head nn; + xs = tail nn; + in if xs == [] then x + else gcd2 x (gcd xs); + +in gcd list + -- cgit v1.2.3