Sem ponto em Haskell

Question

Eu tenho esse código que quero tornar livre de pontos;

(\k t -> chr $ a + flip mod 26 (ord k + ord t -2*a))

Como faço isso?

Também existem algumas regras gerais para o estilo livre de pontos além de "pensar nessa AMD inventar alguma coisa"?

Answer 1

Para transformar uma função

func x y z = (some expression in x, y and z)

em forma livre de ponto, geralmente tento seguir o que é feito até o último parâmetro z e escreva a função como

func x y z = (some function pipeline built using x and y) z

Então eu posso cancelar o zs obter

func x y = (some function pipeline built using x and y)

Então repetir o processo para y e x deve acabar com func em forma livre de ponto. Uma transformação essencial para reconhecer neste processo é:

    f z = foo $ bar z    -- or f z = foo (bar z)
<=> f z = foo . bar $ z
<=> f   = foo . bar

Também é importante lembrar que, com a avaliação parcial, você pode "interromper" o último argumento de uma função:

foo $ bar x y == foo . bar x $ y    -- foo applied to ((bar x) applied to y)

Para sua função específica, considere o fluxo que k e t ir através:

1. Aplicar ord para cada um deles
2. Adicione os resultados
3. Subtrair 2*a
4. Pegue o resultado mod 26
5. Adicione a
6. Aplicar chr

Então, como primeira tentativa de simplificar, obtemos:

func k t = chr . (+a) . (`mod` 26) . subtract (2*a) $ ord k + ord t

Observe que você pode evitar flip usando uma seção em mod, e seções usando - ficar bagunçado em Haskell, então há um subtract função (eles se chocam com a sintaxe para escrever números negativos: (-2) significa negativo 2 e não é o mesmo que subtract 2).

Nesta função, ord k + ord t é um excelente candidato para usar Data.Function.on (link). Este combinador útil nos permite substituir ord k + ord t com uma função aplicada a k e t:

func k t = chr . (+a) . (`mod` 26) . subtract (2*a) $ ((+) `on` ord) k t

Agora estamos muito perto de ter

func k t = (function pipeline) k t

e, portanto

func = (function pipeline)

Infelizmente, Haskell é um pouco confuso quando se trata de compor uma função binária com uma sequência de funções unárias, mas há um truque (vou ver se consigo encontrar uma boa referência para isso) e acabamos com:

import Data.Function (on)

func = ((chr . (+a) . (`mod` 26) . subtract (2*a)) .) . ((+) `on` ord)

O que é quase um belo pipeline de funções sem ponto, exceto por esse truque de composição feia. Definindo o .: operador sugerido nos comentários nesta página, isso cria um pouco para:

import Data.Function (on)

(.:) = (.).(.)

func = (chr . (+a) . (`mod` 26) . subtract (2*a)) .: ((+) `on` ord)

Para polir um pouco mais, você pode adicionar algumas funções ajudantes para separar a letra <-> int conversão do César cifra aritmética. Por exemplo: letterToInt = subtract a . ord

Answer 2

Também existem algumas regras gerais para o estilo livre de pontos além de "pensar nessa AMD inventar alguma coisa"?

Você sempre pode trapacear e usar a ferramenta "PL" da Lambdabot (indo para #Haskell no Freenode ou usando por exemplo GHCI em ácido). Para o seu código, o PL fornece:

((chr . (a +) . flip mod 26) .) . flip flip (2 * a) . ((-) .) . (. ord) . (+) . ord

O que não é realmente uma melhoria se você me perguntar.

Answer 3

Definitivamente, há um conjunto de truques para transformar uma expressão em estilo livre de pontos. Não afirmo ser um especialista, mas aqui estão algumas dicas.

Primeiro, você deseja isolar os argumentos da função no termo mais à direita da expressão. Suas principais ferramentas aqui serão flip e $, usando as regras:

f a b ==> flip f b a
f (g a) ==> f $ g a

Onde f e g são funções e a e b são expressões. Então, para começar:

(\k t -> chr $ a + flip mod 26 (ord k + ord t -2*a))
-- replace parens with ($)
(\k t -> chr $ (a +) . flip mod 26 $ ord k + ord t - 2*a)
-- prefix and flip (-)
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ord k + ord t)
-- prefix (+)
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ (+) (ord k) (ord t))

Agora precisamos conseguir t fora do lado direito. Para fazer isso, use a regra:

f (g a) ==> (f . g) a

E entao:

-- pull the t out on the rhs
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((+) (ord k) . ord) t)
-- flip (.) (using a section)
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((. ord) $ (+) (ord k)) t)
-- pull the k out
(\k t -> chr $ (a +) . flip mod 26 $ flip (-) (2*a) $ ((. ord) . ((+) . ord)) k t)

Agora, precisamos transformar tudo à esquerda de k e t em um grande termo de função, para que tenhamos uma expressão da forma (\k t -> f k t). É aqui que as coisas ficam um pouco impressionantes. Para começar, observe que todos os termos até o último $ são funções com um único argumento, para que possamos compõi -los:

(\k t -> chr . (a +) . flip mod 26 . flip (-) (2*a) $ ((. ord) . ((+) . ord)) k t)

Agora, temos uma função do tipo Char -> Char -> Int que queremos compor com uma função do tipo Int -> Char, produzindo uma função do tipo Char -> Char -> Char. Podemos conseguir isso usando a regra (de aparência muito estranha)

f (g a b) ==> ((f .) . g) a b

Isso nos dá:

(\k t -> (((chr . (a +) . flip mod 26 . flip (-) (2*a)) .) . ((. ord) . ((+) . ord))) k t)

Agora podemos apenas aplicar uma redução beta:

((chr . (a +) . flip mod 26) .) . (flip flip (2*a) . ((-) . ) . ((. ord) . (+) .ord))

Answer 4

Estou assumindo que o objetivo da sua liberação de pontos é tornar o código mais conciso e mais legível. Portanto, acho que é aconselhável fazer também algumas outras refatoras para a simplificação, o que pode facilitar a remoção das variáveis.

(\k t -> chr $ a + flip mod 26 (ord k + ord t - 2*a))

Primeiro de tudo, o flip é desnecessário:

(\k t -> chr $ a + (ord k + ord t - 2*a) `mod` 26)

Em seguida, eu usaria nome e conquista Para levar em consideração uma subfunção utilizável de forma independente:

encode_characters k t = chr $ encode (ord k) (ord t)
encode x y = (x + y - 2*a) `mod` 26 + a

Também dei um nome à primeira expressão para torná -la mais clara e reutilizável. encode_characters agora é fácil de tornar livre de pontos usando a técnica de @nefrubyr:

encode_characters = chr . encode `on` ord

Quanto à segunda expressão, não posso produzir um formulário mais legível do que o mostrado nas outras respostas e todas elas são menos legíveis que a forma de ponto. Portanto, sugeriria parar de refatorar neste momento e admirar a limpeza e a reutilização do código resultante.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

PS: Como exercício, dependendo do contexto do problema, algumas pequenas modificações das interfaces de função (quais dados em que forma são transmitidos para as funções) podem produzir mais simplificações generalizando o problema.

A. Implementar e simplificar a função encode_n_characters :: [Char] -> Char Onde encode_characters k t = encode_n_characters [k, t]. O resultado é mais simples que a função especializada de dois argumentos?

B. Implementar uma função encode' definido via encode' (x + y) = encode x y e reimplementar encode_characters usando esta função. Qualquer uma das funções se torna mais simples? A implementação é mais simples em geral? É encode' mais ou menos reutilizável do que encode?

Answer 5

Conecte -se IRC, #Haskell, e Pergunte Lambdabot!:

<you> @pl (\k t -> chr $ a + flip mod 26 (ord k + ord t -2*a))
<lambdabot> [the answer]