Блог

Я пишу программу для генерации первых k чисел вида

,

где a и b — неотрицательные целые числа.

Алгоритм, который я использую, использует тот факт, что каждое число в этом ряду генерируется путем добавления либо 1, либо sqrt(2) к предыдущему числу в ряду, причем ряд начинается с 0. Мы будем собирать числа в серии в массив, где ожидается, что каждый элемент будет оцениваться лениво по требованию. Первое число в ряду равно 0, поэтому мы инициализируем первый элемент массива с 0. Мы будем поддерживать два указателя i и j, оба начинаются с индекса 0 (первое число в ряду). Следующее число в ряду — min(A[i] 1, A[j] sqrt(2)). Если следующее число в ряду исходит от указателя i, то указатель i будет увеличен (поскольку мы никогда не хотим снова добавлять 1 к [i]) и аналогично, если следующее число в ряду исходит от указателя j, то j будет увеличено, чтобы указать на следующий индекс, т.е. j 1. И i, и j будут увеличены, если A[i] 1 = A[j] sqrt(2).

Я думаю, что приведенный ниже фрагмент содержит приведенный выше алгоритм, однако при запуске кода в ghci похоже, что функция f вызывается повторно с параметрами 1 0 0, и программа никогда не завершается. Я не понимаю, как выполняется этот вызов, хотя кажется, что вызов запускается v A.! i .

 import qualified Data.Array as A 
import Debug.Trace 

compute :: Int -> Int -> Double
compute x y = (fromIntegral x)   (fromIntegral y) * (sqrt 2)

firstK :: Int -> [(Int,Int)]
firstK k = A.elems v where 
    v = A.listArray (0,k-1) $ (0,0):f 1 0 0
    f c i j 
        | c == k = [] 
        | otherwise = traceShow (c,i,j) $
            let (ix,iy) = v A.! i 
                (jx,jy) = v A.! j 
                iv      = compute (ix 1) iy 
                jv      = compute jx (jy 1)
            in  if iv < jv 
                    then (ix 1,iy):f (c 1) (i 1) j 
                else if iv > jv 
                    then (jx,jy 1):f (c 1) i (j 1)
                    else (ix 1,iy):f (c 1) (i 1) (j 1)
 

Вывод —

 λ> firstK 50
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
...
...
 

в ответе chi подробно обсуждается точная проблема с вашим кодом и исправление, которое позволит вам сохранить вашу идею реализации, но получить ответ, на который вы надеетесь. Но я думаю, что также интересно посмотреть, как носитель языка Haskell будет использовать тот же алгоритм: я собираюсь просто использовать собственные списки, а вместо указателя на массив я буду использовать сами указатели списка, чтобы отслеживать, где мы находимся. Это выглядит так:

 vs :: [(Int,Int)]
vs = (0,0) : merge [(a 1, b) | (a, b) <- vs] [(a, b 1) | (a, b) <- vs] where
    compute (a,b) = fromIntegral a   fromIntegral b * sqrt 2
    merge xs@(xh:xt) ys@(yh:yt) = case compare (compute xh) (compute yh) of
        LT -> xh:merge xt ys
        EQ -> xh:merge xt yt
        GT -> yh:merge xs yt
 

В рекурсивном вызове to merge использование xt (вместо xs ) сродни увеличению вашего i указателя; использование yt (вместо ys ) сродни увеличению вашего j указателя.

Одна приятная вещь vs заключается в том, что вам не нужно заранее объявлять, сколько пар вы хотите — вы просто получаете их бесконечный список (вплоть до проблем с округлением при использовании Double for compute , конечно!). Код также значительно короче. Вот пример, выполняемый в ghci:

 > take 10 vs
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(4,0)]
 

Проблема arrayList в том, что слишком рано приводит к тому, что весь корешок списка создается до фактического построения массива. Это делает цикл рекурсии вечным.

Однако мы можем исправить это, используя вспомогательную функцию следующим образом.

 -- A spine-lazy version of arrayList
arrayListLazy :: (Int, Int) -> [a] -> A.Array Int a
arrayListLazy (lo,hi) xs = A.array (lo,hi) $ go lo xs
   where
   go i _ | i > hi = []
   go i ~(e:ys) = (i, e) : go (succ i) ys

firstK :: Int -> [(Int,Int)]
firstK k = A.elems v where 
    v = arrayListLazy (0,k-1) $ (0,0):f 1 0 0
    f c i j 
        | c == k = [] 
        | otherwise = traceShow (c,i,j) $
            let (ix,iy) = v A.! i 
                (jx,jy) = v A.! j 
                iv      = compute (ix 1) iy 
                jv      = compute jx (jy 1)
            in  if iv < jv 
                    then (ix 1,iy):f (c 1) (i 1) j 
                else if iv > jv 
                    then (jx,jy 1):f (c 1) i (j 1)
                    else (ix 1,iy):f (c 1) (i 1) (j 1)
 

Небольшой тест:

 > firstK 10
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(4,0)]
 

Альтернативный подход, использующий ту же идею,

 firstK k = take k $ l
  where l = (0,0) : unfoldr ((i,j) -> Just $ case compare (uncurry compute $ first (1 ) $ l!!i) (uncurry compute $ second (1 ) $ l!!j) of
          LT -> (first (1 ) $ l!!i, (i 1,j))
          EQ -> (first (1 ) $ l!!i, (i 1,j 1))
          GT -> (second (1 ) $ l!!j, (i,j 1))) (0,0)
 

Не особенно аккуратно, но вы можете видеть, к чему это приводит, в частности, сопоставление с образцом case compare _ _ of ... imo лучше, чем if a > b else if a < b else .. .

РЕДАКТИРОВАТЬ: хотя и хуже по времени.