Search code examples
haskellgreatest-common-divisor

Trying to find GCD with Haskell. Where is the error in my code?


As an exercise, I'm trying to write this by myself but I'm stuck and don't know where the error is in my code.

module Hf where

--sumSquaresTo :: Integer -> Integer
--sumSquaresTo x = sum [ n^2 | n <- [1..x] ]

divides a b = b `mod` a == 0

divisors a = [n | n <- [1..a], n `divides` a ]


lnko :: Integer -> Integer -> Integer
lnko a b = [n | n <- [1..max(a b)], (n `divides` a) && (n `divides` b) ]

GHCI output:

error:
    * Couldn't match expected type `Integer'
                  with actual type `[a0 -> a0]'
    * In the expression:
        [n | n <- [1 .. max (a b)], (n `divides` a) && (n `divides` b)]
      In an equation for `lnko':
          lnko a b
            = [n | n <- [1 .. max (a b)], (n `divides` a) && (n `divides` b)]
   |
12 | lnko a b = [n | n <- [1..max(a b)], (n `divides` a) && (n `divides` b) ]
   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error:
    * Couldn't match expected type `Integer -> a0'
                  with actual type `Integer'
    * The function `a' is applied to one argument,
      but its type `Integer' has none
      In the first argument of `max', namely `(a b)'
      In the expression: max (a b)
   |
12 | lnko a b = [n | n <- [1..max(a b)], (n `divides` a) && (n `divides` b) ]
   |                              ^^^

error:
    * Couldn't match expected type `a0 -> a0'
                  with actual type `Integer'
    * In the second argument of `divides', namely `a'
      In the first argument of `(&&)', namely `(n `divides` a)'
      In the expression: (n `divides` a) && (n `divides` b)
    * Relevant bindings include
        n :: a0 -> a0
          (bound at C:\\Users\erdos\Desktop\haskell\hazi1.hs:12:17)
   |
12 | lnko a b = [n | n <- [1..max(a b)], (n `divides` a) && (n `divides` b) ]
   |                                                  ^

error:
    * Couldn't match expected type `a0 -> a0'
                  with actual type `Integer'
    * In the second argument of `divides', namely `b'
      In the second argument of `(&&)', namely `(n `divides` b)'
      In the expression: (n `divides` a) && (n `divides` b)
    * Relevant bindings include
        n :: a0 -> a0
          (bound at C:\\Users\erdos\Desktop\haskell\hazi1.hs:12:17)
   |
12 | lnko a b = [n | n <- [1..max(a b)], (n `divides` a) && (n `divides` b) ]
   |                                                                     ^
Failed, no modules loaded.

Solution

  • Well, there are 2 mistakes.

    1. In Haskell, you do not write max(a b), but simply max a b. This is called currying.

    2. Your function actually locates all common factors. For instance:

      λ lnko 8 16
      [1,2,4,8]
      

      If you amend the type signature accordingly, it will work. Or you may select one of the factors somehow.

    Overall, this is great code. Keep going!