a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

git clone: git://git.pablopie.xyz/a-conjecture-of-mine
Log
Files
Refs

Commit: 1d939a73ebaa54ec82c586544ce9f4e5d7cdc933
Parent: 04c9f23dbc51a6e4850c4928c0c055dc05b7b4a0
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Sun, 8 Dec 2019 13:47:22 -0200

Optimized the Haskell implementation by using tabled recursion.

Diffstat

4 files changed, 168 insertions, 151 deletions

Status	File Name	N° Changes	Insertions	Deletions
Modified	Haskell/.gitignore	6	3	3
Modified	Haskell/app/Main.hs	111	63	48
Modified	Haskell/package.yaml	66	34	32
Modified	Haskell/stack.yaml	136	68	68

diff --git a/Haskell/.gitignore b/Haskell/.gitignore
@@ -1,4 +1,4 @@
-.stack-work
-.idea
-*.cabal
+.stack-work
+.idea
+*.cabal
 stack.yaml 
\ No newline at end of file

diff --git a/Haskell/app/Main.hs b/Haskell/app/Main.hs
@@ -1,49 +1,64 @@
--- The following program is a simple test for the following conjecture:
-
--- Let S: N -> N be the sum of the digits of a positive integer.
--- For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.
-
-module Main where
-
-import Numeric
-import Numeric.Natural
-import System.Environment
-import System.Exit
-import Control.Monad(foldM)
-
-main :: IO Int
-main = do
-    args <- getArgs
-
-    if length args > 0
-        then case readDec (args !! 0) :: [(Natural, String)] of
-            [(max, "")] -> if counter' max then exitFailure else exitSuccess
-                    
-            _ -> exitInvalidInput
-            
-        else exitInvalidInput
-
-sum' :: Natural -> Natural
-sum' n
-    | n < 10 = n
-    | otherwise = (n `mod` 10) + sum' (n `div` 10)
-
-test' :: Natural -> Natural -> Bool
-test' a b = let s(x) = fromEnum $ sum' x in (s(a + b) - s(a) - s(b)) `mod` 9 == 0
-
-counter' :: Natural -> Bool
-counter' max = case foldM f max [0..max] of
-    Left _  -> True
-    Right _ -> False
-    where f a b = iter' b max
-
-iter' :: Natural -> Natural -> Either () Natural
-iter' a max = case foldM f a [a..max] of
-    Left _  -> Left ()
-    Right _ -> Right (a - 1)
-    where f i b
-            | test' a b = Right (i + 1)
-            | otherwise = Left ()
-
-exitInvalidInput :: IO Int
+-- The following program is a simple test for the following conjecture:
+
+-- Let S: N -> N be the sum of the digits of a positive integer.
+-- For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.
+
+module Main where
+
+import Numeric
+import Numeric.Natural
+import System.Environment
+import System.Exit
+import Control.Monad (foldM)
+import Data.Map (Map, insert, lookup, empty)
+import qualified Data.Map as Map
+
+main :: IO Int
+main = do
+    args <- getArgs
+
+    if length args > 0
+        then case readDec (args !! 0) :: [(Natural, String)] of
+            [(max, "")] -> if counter' max empty then exitFailure else exitSuccess
+                    
+            _ -> exitInvalidInput
+            
+        else exitInvalidInput
+
+sum' :: Natural -> Int
+sum' n
+    | n < 10 = fromEnum n
+    | otherwise = fromEnum (n `mod` 10) + sum' (n `div` 10)
+
+test' :: Natural -> Natural -> Map Natural Int -> Maybe (Map Natural Int)
+test' a b sums =
+    case lookup a of
+        Just sa ->
+            case lookup b of
+                Just sb ->
+                    case lookup $ a + b of
+                        Just sab ->
+                            if (sab - sa - sb) `mod` 9 == 0
+                                then Just sums
+                                else Nothing
+                        Nothing  -> retry $ a + b
+                Nothing -> retry b
+        Nothing -> retry a
+
+    where retry x = test' a b $ insert x (sum' x) sums
+          lookup x = Map.lookup x sums
+
+counter' :: Natural -> Map Natural Int -> Bool
+counter' max sums =
+    case foldM f (max, sums) [0..max] of
+        Nothing  -> True
+        Just _   -> False
+    where f (a, sums) b = iter' b max sums
+
+iter' :: Natural -> Natural -> Map Natural Int -> Maybe (Natural, Map Natural Int)
+iter' a max sums = foldM f sums [a..max] >>= continue
+    where continue updated = Just (a - 1, updated)
+          f sums b = test' a b sums
+
+exitInvalidInput :: IO Int
 exitInvalidInput = exitWith (ExitFailure 2) 
\ No newline at end of file

diff --git a/Haskell/package.yaml b/Haskell/package.yaml
@@ -1,31 +1,33 @@
-name:                conjecture
-version:             1.0.0.0
-license:             BSD3
-author:              "GarkGarcia"
-maintainer:          "thiago.brevidelli.garcia@protonmail.com"
-copyright:           "2019 GarkGarcia"
-
-extra-source-files: []
-
-# Metadata used when publishing your package
-# synopsis:            Short description of your package
-# category:            Web
-
-# To avoid duplicated efforts in documentation and dealing with the
-# complications of embedding Haddock markup inside cabal files, it is
-# common to point users to the README.md file.
-description: This program is a simple test for a little conjecture of mine.
-
-dependencies:
-  - base >= 4.7 && < 5
-
-executables:
-  haskell:
-    main: Main.hs
-    source-dirs: app
-    ghc-options:
-      - -threaded
-      - -rtsopts
-      - -with-rtsopts=-N
-      - -O
-    dependencies: []-
\ No newline at end of file
+name:                conjecture
+version:             1.0.0.0
+license:             MIT
+author:              "GarkGarcia"
+maintainer:          "gark.garcia@protonmail.com"
+copyright:           "2019 GarkGarcia"
+
+extra-source-files: []
+
+# Metadata used when publishing your package
+# synopsis:            Short description of your package
+# category:            Web
+
+# To avoid duplicated efforts in documentation and dealing with the
+# complications of embedding Haddock markup inside cabal files, it is
+# common to point users to the README.md file.
+description: This program is a simple test for a little conjecture of mine.
+
+dependencies:
+  - base >= 4.7 && < 5
+  - containers == 0.6.2.1
+
+executables:
+  haskell:
+    main: Main.hs
+    source-dirs: app
+    ghc-options:
+      - -threaded
+      - -rtsopts
+      - -with-rtsopts=-N
+      - -O
+    dependencies:
+      - containers == 0.6.2.1+
\ No newline at end of file

diff --git a/Haskell/stack.yaml b/Haskell/stack.yaml
@@ -1,68 +1,68 @@
-# This file was automatically generated by 'stack init'
-#
-# Some commonly used options have been documented as comments in this file.
-# For advanced use and comprehensive documentation of the format, please see:
-# https://docs.haskellstack.org/en/stable/yaml_configuration/
-
-# Resolver to choose a 'specific' stackage snapshot or a compiler version.
-# A snapshot resolver dictates the compiler version and the set of packages
-# to be used for project dependencies. For example:
-#
-# resolver: lts-3.5
-# resolver: nightly-2015-09-21
-# resolver: ghc-7.10.2
-#
-# The location of a snapshot can be provided as a file or url. Stack assumes
-# a snapshot provided as a file might change, whereas a url resource does not.
-#
-# resolver: ./custom-snapshot.yaml
-# resolver: https://example.com/snapshots/2018-01-01.yaml
-resolver: lts-13.10
-
-# User packages to be built.
-# Various formats can be used as shown in the example below.
-#
-# packages:
-# - some-directory
-# - https://example.com/foo/bar/baz-0.0.2.tar.gz
-# - location:
-#    git: https://github.com/commercialhaskell/stack.git
-#    commit: e7b331f14bcffb8367cd58fbfc8b40ec7642100a
-# - location: https://github.com/commercialhaskell/stack/commit/e7b331f14bcffb8367cd58fbfc8b40ec7642100a
-#  subdirs:
-#  - auto-update
-#  - wai
-packages:
-  - .
-# Dependency packages to be pulled from upstream that are not in the resolver
-# using the same syntax as the packages field.
-# (e.g., acme-missiles-0.3)
-extra-deps:
-  - conduit-1.2.13.1@sha256:afd4db7fe66ae7af3d418e1a932384a8dee08df2f6299cca80e53ba964ce1228
-  - conduit-extra-1.1.17@sha256:a4e6f476ba86db2c7cb76993b43b2a156b010de2917d239af66f9d7e7599e269
-  - resourcet-1.1.11@sha256:096a3db6774a728bbe264e3e25c4e40d60e527ebd4b90c0b311deaa8d4cf4f27
-  - streaming-commons-0.1.19@sha256:3a02f84578f75eac1425dca877f8d697b68d379a21970c1dad96196620404803
-
-# Override default flag values for local packages and extra-deps
-# flags: {}
-
-# Extra package databases containing global packages
-# extra-package-dbs: []
-
-# Control whether we use the GHC we find on the path
-# system-ghc: true
-#
-# Require a specific version of stack, using version ranges
-# require-stack-version: -any # Default
-# require-stack-version: ">=1.9"
-#
-# Override the architecture used by stack, especially useful on Windows
-# arch: i386
-# arch: x86_64
-#
-# Extra directories used by stack for building
-# extra-include-dirs: [/path/to/dir]
-# extra-lib-dirs: [/path/to/dir]
-#
-# Allow a newer minor version of GHC than the snapshot specifies
-# compiler-check: newer-minor
+# This file was automatically generated by 'stack init'
+#
+# Some commonly used options have been documented as comments in this file.
+# For advanced use and comprehensive documentation of the format, please see:
+# https://docs.haskellstack.org/en/stable/yaml_configuration/
+
+# Resolver to choose a 'specific' stackage snapshot or a compiler version.
+# A snapshot resolver dictates the compiler version and the set of packages
+# to be used for project dependencies. For example:
+#
+# resolver: lts-3.5
+# resolver: nightly-2015-09-21
+# resolver: ghc-7.10.2
+#
+# The location of a snapshot can be provided as a file or url. Stack assumes
+# a snapshot provided as a file might change, whereas a url resource does not.
+#
+# resolver: ./custom-snapshot.yaml
+# resolver: https://example.com/snapshots/2018-01-01.yaml
+resolver: lts-13.10
+
+# User packages to be built.
+# Various formats can be used as shown in the example below.
+#
+# packages:
+# - some-directory
+# - https://example.com/foo/bar/baz-0.0.2.tar.gz
+# - location:
+#    git: https://github.com/commercialhaskell/stack.git
+#    commit: e7b331f14bcffb8367cd58fbfc8b40ec7642100a
+# - location: https://github.com/commercialhaskell/stack/commit/e7b331f14bcffb8367cd58fbfc8b40ec7642100a
+#  subdirs:
+#  - auto-update
+#  - wai
+packages:
+  - .
+# Dependency packages to be pulled from upstream that are not in the resolver
+# using the same syntax as the packages field.
+# (e.g., acme-missiles-0.3)
+extra-deps: []
+#  - conduit-1.2.13.1@sha256:afd4db7fe66ae7af3d418e1a932384a8dee08df2f6299cca80e53ba964ce1228
+#  - conduit-extra-1.1.17@sha256:a4e6f476ba86db2c7cb76993b43b2a156b010de2917d239af66f9d7e7599e269
+#  - resourcet-1.1.11@sha256:096a3db6774a728bbe264e3e25c4e40d60e527ebd4b90c0b311deaa8d4cf4f27
+#  - streaming-commons-0.1.19@sha256:3a02f84578f75eac1425dca877f8d697b68d379a21970c1dad96196620404803
+
+# Override default flag values for local packages and extra-deps
+# flags: {}
+
+# Extra package databases containing global packages
+# extra-package-dbs: []
+
+# Control whether we use the GHC we find on the path
+# system-ghc: true
+#
+# Require a specific version of stack, using version ranges
+# require-stack-version: -any # Default
+# require-stack-version: ">=1.9"
+#
+# Override the architecture used by stack, especially useful on Windows
+# arch: i386
+# arch: x86_64
+#
+# Extra directories used by stack for building
+# extra-include-dirs: [/path/to/dir]
+# extra-lib-dirs: [/path/to/dir]
+#
+# Allow a newer minor version of GHC than the snapshot specifies
+# compiler-check: newer-minor