Traduzindo “Matters Por funcionais de programação” em Haskell

Question

Para o enriquecimento cultural e intelectual, eu decidi aprender um pouco de Haskell. Estive lendo Hughes' 'Por programação funcional Matters' estou tentando traduzir seu código em verdadeira Haskell. Anexei um pouco da minha tentativa abaixo (para as partes numéricas do papel; o algoritmo alfa-beta é ainda mais interessante, mas eu também teria que escrever um avaliador de jogo a partir do zero!).

Neste ponto, tem sido mais de um exercício de sintaxe Haskell que qualquer outra coisa. Já fiz coisas simples como traduzir repeat no iterate nativa Haskell, traduzir algumas funções que usaram um monte de parênteses para composição de função (tornando-os mais no processo de livre-ponto), etc.

Mas o meu código certamente funciona, e gostaria de saber se é suficientemente "Haskell-ish". os peritos podem lá fora me dar algumas dicas?

-- 4.1 Newton-Raphson square roots
next n x = (x + n/x)/2.0

-- -- this is "iterate::(a->a)->a->[a]"
-- repeat f a  = a : iterate f (f a)

within eps (a:b:rest) = 
  if abs(a-b) <= eps 
    then b
    else within eps (b:rest)

sqroot a0 eps n = within eps (iterate (next n) a0)

relative eps (a:b:rest) = 
  if abs(a-b) <= eps*abs(b)
    then b
    else relative eps (b:rest)

relativesqrt a0 eps n = relative eps (iterate (next n) a0)

-- 4.2 numerical differentiation

easydiff f x h = (f (x+h) - f x) / h

differentiate h0 f x = map (easydiff f x) (iterate (/2) h0)

-- diff1a h0 eps f x = within eps (differentiate h0 f x)
diff1 h0 eps f = within eps . differentiate h0 f 

elimerror n (a:b:rest) = (b*(2**n)-a)/(2**n-1) : elimerror n (b:rest)

-- need fromIntegral to make a non-integer out of the Int which comes out of round
order (a:b:c:rest) =  fromIntegral (round (logBase 2 ((a-c)/(b-c)-1)))

improve s = elimerror (order s) s 

--diff2a h0 eps f x = within eps (improve (differentiate h0 f x))
diff2 h0 eps f = within eps . improve . differentiate h0 f 

--super s = map second (iterate improve s) -- how can we make this point-free?
super :: (RealFrac t, Floating t) => [t] -> [t] 
           -- w/o this it wants to be [double]->[double]
super = map second . iterate improve

-- second (a:b:rest) = b
second = head . tail

diff3 h0 eps f = within eps . super . differentiate h0 f

-- 4.3 integration

easyintegrate f a b = (f a + f b)*(b-a)/2

-- addpair becomes (uncurry (+))

integrate f a b = integ f a b (f a) (f b) 

integ f a b fa fb = 
  (fa+fb)*(b-a)/2 : map (uncurry (+)) (zip (integ f a m fa fm) (integ f m b fm fb))
  where m = (a+b)/2 
        fm = f m 

-- test: following should be about pi
approxpi eps = within eps (improve (integrate (\x -> 4/(1+x*x)) 0 1))
superpi eps = within eps (super (integrate (\x -> 4/(1+x*x)) 0 1))

-- is there any way to keep track of the number of iterations? state monad, but seems like a lot of work...\

Answer 1

4,1 Newton-Raphson raízes quadradas

Estas duas linhas

sqroot a0 eps n = within eps (iterate (next n) a0)
relativesqrt a0 eps n = relative eps (iterate (next n) a0)

são quase idênticos, assim que você poderia coisas abstratas um passo além:

sqroot method a0 eps n = method eps (iterate (next n) a0)
relativesqrt = sqroot relative
withinsqrt   = sqroot within

4,2 numérica diferenciação

Eu não vejo o ponto em ter h0 como um argumento para a função differentiate como é apenas o ponto de partida para a sequência limitando 0. (O mesmo não é verdade para a0 no caso Newton-Rhapson, onde o ponto de partida pode ser importante).

Eu acho que é igualmente apropriado abstrato sobre a taxa de que esse limite se aproxima de zero:

differentiate rate f x = map (easydiff f x) (iterate rate 1)

É claro que se pode fazer as duas coisas:

differentiate rate h0 f x = map (easydiff f x) (iterate rate h0)

Em qualquer caso, é uma decisão muito arbitrária.

4.2 Integração

Você pode usar

zipWith (+) (integ f a m fa fm) (integ f m b fm fb)

em vez de

map (uncurry (+)) (zip (integ f a m fa fm) (integ f m b fm fb))

que eu acho que é mais legível.

Answer 2

Para within e relative eu usaria notação guardado:

within eps (a:b:rest)
  | abs(a-b)<=eps = b
  | otherwise = within eps (b:rest)

Para second, você poderia escrever !! 1. Especialmente essa última é preferência pessoal, eu acho.

Você também deve dar as assinaturas de tipo.

Editar : Se você estiver em ofuscação, tente:

within :: (Ord a, Num a) => a -> [a] -> a
within eps l@(_:xs) = snd. head . filter ((<= eps) . fst) $ zip zs xs
   where
    zs = zipWith (\ a b -> abs (a-b)) l xs

(Tipo marcada, não testado - e eu nunca sei se eu acertar o filtro ou se tiver de ser negada;)

Answer 3

Roger Costello escreveu um resumo duas partes do John Hughes papel traduzir o código Miranda original para Haskell. Aqui estão primeira parte e parte dois de sua writeup.

Answer 4

Então, esse é um straight-across tradução (ou seja, tentar manter o código procurando o mais semelhante possível) ou um incorporado (ou seja, fazer tantos ajustes idiomáticas para o código quanto possível, sem fazer os exemplos mais difícil de entender , é claro) um?

Assumindo que este "projeto" ainda está em curso ......