GCD via Nix expressions

1 files changed, 40 insertions, 0 deletions

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
+