From 89375f7490377b396726b159f60ba4b914c85285 Mon Sep 17 00:00:00 2001
From: Igor Pashev <pashev.igor@gmail.com>
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

(limited to '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