Traduzindo “Matters Por funcionais de programação” em Haskell
-
05-07-2019 - |
Pergunta
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...\
Nenhuma solução correta
Outras dicas
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
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.
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;)
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.
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 ......