Вопросы Теги

Haskell: Equation Expander 1+ (1+ (1+ (1+ (…)))) = ∞

Есть ли здесь существует расширитель уравнений для Haskell?

Что-то вроде foldr.com : 1+ (1+ (1+ (1+ (…)))) = ∞

Я новичок в Haskell Мне трудно понять, почему одни уравнения предпочтительнее других. Думаю, мне поможет, если я смогу увидеть расширенные уравнения.

Например, я обнаружил, что foldr vs foldl трудно понять сначала, пока я не увидел, что они расширены. 

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z xs = go xs
             where
               go []     = z
               go (y:ys) = y `k` go ys

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

Из определений я вижу, что foldr расширяется следующим образом: 

foldr (+) 0 [1..1000000] -->
1 + (foldr (+) 0 [2..1000000]) -->
1 + (2 + (foldr (+) 0 [3..1000000])) -->
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) -->
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) -->

и foldl расширяется следующим образом: 

foldl (+) 0 [1..1000000] -->
foldl (+) (foldl (+) 0 [1]) [2..1000000]) --> 
foldl (+) (foldl (+) (foldl (+) 0 [1])) [3..1000000]) -->

или из Haskell Wiki на foldr fold foldl ': 

let z1 =  0 + 1
in foldl (+) z1 [2..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
in foldl (+) z2 [3..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
in foldl (+) z3 [4..1000000] -->

let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
in foldl (+) z4 [5..1000000] -->

Однако мне сложно понять, почему в более крупных уравнениях все работает именно так, как в Haskell. Например, первая функция сита использует 1000 фильтров, а вторая функция сита требует всего 24, чтобы найти простое число 1001. 

primes = sieve [2..]
   where
    sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0] 



primes = 2: 3: sieve (tail primes) [5,7..]
   where 
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]  
                                    -- or:  filter ((/=0).(`rem`p)) t
                      where (h,~(_:t)) = span (< p*p) xs

Haskell Wiki on Primes

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

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

Есть ли инструмент для расширения выражений Haskell?

13
задан Community 23 May 2017 в 10:24
поделиться