Пытаюсь найти GCD с помощью Haskell. Где ошибка в моем коде?

Question

В качестве упражнения я пытаюсь написать это самостоятельно, но застрял и не знаю, где находится ошибка в моем коде.

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:

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.

Answer 1

Ну, есть две ошибки.

1. В Хаскеле вы пишете не max(a b), а просто max a b. Это называется curry .

2. Ваша функция фактически обнаруживает все общие факторы. Например:

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

   Если вы соответствующим образом измените сигнатуру типа, она будет работать. Или вы можете как-то выбрать один из факторов.

В целом, это отличный код. Продолжай!

Answer 2

Типы не совпадают. Действительно, в вашей функции:

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

Вы здесь возвращаете список, поскольку используете его понимание. Кроме того, вы допустили некоторые синтаксические ошибки. Например, max (a b) означает, что вы выполняете приложение функции с a в качестве функции и b в качестве параметра. Это должно быть max a b.

. Вы можете переписать это следующим образом:

lnko :: Integer -> Integer -> Integer
lnko a b = <b>maximum</b> [n | n <- [1..<b>min a b</b>], n `divides` a, n `divides` b ]

Но, тем не менее, здесь вы используете метод, при котором вы перебираете все возможные делители, чтобы найти самый большой. Например, вы можете использовать евклидов алгоритм [wiki] , который обычно превосходит линейный поиск:

lnko :: Integral i => i -> i -> i
lnko a 0 = a
lnko a b = lnko b (mod a b)

Это также будет более безопасно, например, еслиВы используете отрицательные числа в параметрах.