Sep. 6th, 2014

xacid: (Default)
Недавно один коллега на работе, рассказывая о хаскеле в сравнении с другими функциональными языками (это был целый обзорный доклад такой у него для местной публики) высказал такое утверждение что дескать в хаскеле ну никак нельзя избавиться от ленивых вычислений и строго вычислить какое нибудь выражение. Я был несколько удивлен тогда такой информацией, но посколько хаскель знаю плохо, спорить не стал. И вот на днях, изучая издание "Algorithms. A functional approach" аж от 1999го года выпуска, где именно на хаскеле учат эффективно реализовывать эти самые алгоритмы, наткнулся на такую информацию что на самом деле в хаскеле есть стандартная функция-оператор $! которая делает ничто иное как строго вычисляет значение.

Более того, без этой самой возможности строго вычислить значение (то есть без оператора $!) в хаскеле вообще в принципе не работает хвостовая рекурсия - невычисленные значения лениво накапливаются в стеке.

Самое забавное это когда нужно строго вычислить сразу например пару значений:
prodsum n = x + y where
  (x, y) = f n (1,0)
  f n (a,b) | n == 0 = (a,b)
    | otherwise = (f (n-1)) $!
      ((n*a) `with` (n+b))
  with a b = ((,) $! a) $! b

(это мое решение для упражнения из книги :

3.4 Consider the following program:

prodsum x = prod x + sum x

prod 0 = 1
prod n = n * prod (n - 1)

sum 0 = 0
sum n = n + sum (n - 1)

(a) Change the definitions of sum and prod into tail-recursive ones.
(b) Using the Burstall-Darlington transformation system, write a new definition of prodsum (using tuples) such that the result is computed in one pass.
(c) Change this definition into one that avoids using tuples and which is tail- recursive.)

Но самое правильное решение конечно такое:
prodsum' x = f x 0 1 where
  f 0 x y = x + y
  f n x y = (f (n-1) $! (n+x)) $! (n*y)

Profile

xacid: (Default)
xacid

April 2021

S M T W T F S
    123
45678910
11121314151617
18192021222324
252627282930 

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 9th, 2025 06:37 pm
Powered by Dreamwidth Studios