"Lembrando" valores na programação funcional

Decidi assumir a tarefa de aprender programação funcional. Até agora tem sido uma explosão, e eu 'vi a luz' por assim dizer. Infelizmente, eu realmente não conheço nenhum programador funcional do qual possa responder perguntas. Apresentando o Stack Exchange.

Estou fazendo um curso de desenvolvimento de web / software, mas meu instrutor não está familiarizado com programação funcional. Ele está bem comigo, e me pediu para ajudá-lo a entender como funciona para que ele possa ler melhor meu código.

Decidi que a melhor maneira de fazer isso seria ilustrando uma função matemática simples, como aumentar um valor a uma potência. Em teoria, eu poderia facilmente fazer isso com uma função predefinida, mas isso derrotaria o objetivo de um exemplo.

Enfim, estou tendo alguma dificuldade em descobrir como manter um valor. Como esta é uma programação funcional, não posso mudar de variável. Se eu codificasse isso imperativamente, ficaria assim:

(A seguir, todos os pseudocódigos)

f(x,y) {
  int z = x;
  for(int i = 0, i < y; i++){
    x = x * z;
  }
  return x;
}

Na programação funcional, eu não tinha certeza. Isto é o que eu vim com:

f(x,y,z){
  if z == 'null',
    f(x,y,x);
  else if y > 1,
    f(x*z,y-1,z);
  else
    return x;
}

Isto está certo? Eu preciso manter um valor, znos dois casos, mas não tinha certeza de como fazer isso na programação de funções. Em teoria, do jeito que eu fiz isso funciona, mas eu não tinha certeza se estava 'certo'. Tem algum jeito melhor de fazer isso?

Primeiro de tudo, parabéns por "ver a luz". Você fez do mundo do software um lugar melhor, expandindo seus horizontes.

Segundo, honestamente, não há como um professor que não entende de programação funcional ser capaz de dizer algo útil sobre o seu código, além de comentários triviais, como "a indentação parece". Isso não é tão surpreendente em um curso de desenvolvimento web, pois a maioria do desenvolvimento web é feita usando HTML / CSS / JavaScript. Dependendo do quanto você realmente se preocupa em aprender o desenvolvimento da Web, você pode se esforçar para aprender as ferramentas que seu professor está ensinando (por mais doloroso que seja isso - eu sei por experiência própria).

Para abordar a questão declarada: se seu código imperativo usa um loop, é provável que seu código funcional seja recursivo.

(* raises x to the power of y *)
fun pow (x: real) (y: int) : real = 
    if y = 1 then x else x * (pow x (y-1))

Observe que esse algoritmo é realmente mais ou menos idêntico ao código imperativo. De fato, pode-se considerar o loop acima como um açúcar sintático para processos recursivos iterativos.

Como uma observação lateral, não há necessidade de um valor zno seu código imperativo ou funcional. Você deveria ter escrito sua função imperativa da seguinte maneira:

def pow(x, y):
    var ret = 1
    for (i = 0; i < y; i++)
         ret = ret * x
    return ret

em vez de alterar o significado da variável x.

Este é realmente apenas um adendo à resposta de Gardenhead, mas eu gostaria de ressaltar que há um nome para o padrão que você está vendo: dobrar.

Na programação funcional, uma dobra é uma maneira de combinar uma série de valores que "lembram" um valor entre cada operação. Considere adicionar imperativamente uma lista de números:

def sum_all(xs):
  total = 0
  for x in xs:
    total = total + x
  return total

Tomamos uma lista de valores xse um estado inicial de 0(representado por totalneste caso). Então, para cada xno xs, nós combinamos esse valor com o estado atual de acordo com alguma operação combinando (neste caso disso), e usar o resultado como o novo estado. Em essência, sum_all([1, 2, 3])é equivalente a (3 + (2 + (1 + 0))). Esse padrão pode ser extraído em uma função de ordem superior , uma função que aceita funções como argumentos:

def fold(items, initial_state, combiner_func):
  state = initial_state
  for item in items:
    state = combiner_func(item, state)
  return state

def sum_all(xs):
  return fold(xs, 0, lambda x y: x + y)

Essa implementação de foldainda é imperativa, mas também pode ser feita recursivamente:

def fold_recursive(items, initial_state, combiner_func):
  if not is_empty(items):
    state = combiner_func(initial_state, first_item(items))
    return fold_recursive(rest_items(items), state, combiner_func)
  else:
    return initial_state

Expressa em termos de dobra, sua função é simplesmente:

def exponent(base, power):
  return fold(repeat(base, power), 1, lambda x y: x * y))

... onde repeat(x, n)retorna uma lista de ncópias de x.

Muitas linguagens, particularmente aquelas voltadas para a programação funcional, oferecem dobragem em sua biblioteca padrão. Até o Javascript fornece sob o nome reduce. Em geral, se você estiver usando a recursão para "lembrar" um valor em algum tipo de loop, provavelmente desejará uma dobra.

Esta é uma resposta suplementar para ajudar a explicar mapas e dobras. Para os exemplos abaixo, usarei esta lista. Lembre-se, esta lista é imutável, portanto nunca mudará:

var numbers = [1, 2, 3, 4, 5]

Vou usar números nos meus exemplos porque eles levam a códigos de fácil leitura. Lembre-se, no entanto, as dobras podem ser usadas para qualquer coisa que um loop imperativo tradicional possa ser usado.

Um mapa pega uma lista de algo e uma função e retorna uma lista que foi modificada usando a função. Cada item é passado para a função e se torna o que a função retornar.

O exemplo mais fácil disso é apenas adicionar um número a cada número em uma lista. Vou usar o pseudocódigo para torná-lo independente de idioma:

function add-two(n):
    return n + 2

var numbers2 =
    map(add-two, numbers) 

Se você imprimisse numbers2, veria [3, 4, 5, 6, 7]qual é a primeira lista com 2 adicionadas a cada elemento. Observe que a função add-twofoi atribuída mappara uso.

As dobras s são semelhantes, exceto que a função que você precisa fornecer a elas deve receber 2 argumentos. O primeiro argumento é geralmente o acumulador (na dobra esquerda, que é o mais comum). O acumulador são os dados que são transmitidos durante o loop. O segundo argumento é o item atual da lista; assim como acima para a mapfunção.

function add-together(n1, n2):
    return n1 + n2

var sum =
    fold(add-together, 0, numbers)

Se você imprimisse sum, veria a soma da lista de números: 15.

Aqui estão os argumentos para foldfazer:

1. Esta é a função que estamos dando a dobra. A dobra passará a função do acumulador atual e o item atual da lista. O que quer que a função retorne se tornará o novo acumulador, que será passado para a função na próxima vez. É assim que você "lembra" dos valores quando faz um loop no estilo FP. Eu dei uma função que pega 2 números e os adiciona.

2. Este é o acumulador inicial; o que o acumulador inicia como antes de qualquer item da lista ser processado. Quando você soma números, qual é o total antes de adicionar números? 0, que eu passei como o segundo argumento.

3. Por fim, como no mapa, também passamos na lista de números para processamento.

Se as dobras ainda não fazem sentido, considere isso. Quando você escreve:

# Notice I passed the plus operator directly this time, 
#  instead of wrapping it in another function. 
fold(+, 0, numbers)

Você está basicamente colocando a função passada entre cada item na lista e adicionando o acumulador inicial à esquerda ou à direita (dependendo se é uma dobra esquerda ou direita), então:

[1, 2, 3, 4, 5]

Torna-se:

0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).

O que equivale a 15.

Use a mapquando desejar transformar uma lista em outra lista, do mesmo tamanho.

Use a foldquando desejar transformar uma lista em um único valor, como somar uma lista de números.

Como o @Jorg apontou nos comentários, o "valor único" não precisa ser algo simples como um número; pode ser qualquer objeto único, incluindo uma lista ou uma tupla! O jeito que eu realmente clicou nas dobras para mim foi definir um mapa em termos de dobra. Observe como o acumulador é uma lista:

function map(f, list):
    fold(
        function(xs, x): # xs is the list that has been processed so far
            xs.add( f(x) ) # Add returns the list instead of mutating it
        , [] # Before any of the list has been processed, we have an empty list
        , list) 

Honestamente, depois de entender cada um, você perceberá que quase todos os ciclos podem ser substituídos por uma dobra ou um mapa.

É difícil encontrar bons problemas que não possam ser resolvidos com a funcionalidade de criação. E se estiver embutido, deve ser usado como exemplo de bom estilo na linguagem x.

No haskell, por exemplo, você já tem a função (^)no Prelude.

Ou se você quiser fazer isso de forma mais programática product (replicate y x)

O que estou dizendo é que é difícil mostrar os pontos fortes de um estilo / idioma se você não usar os recursos que ele fornece. No entanto, pode ser um bom passo para mostrar como funciona nos bastidores, mas acho que você deve codificar da melhor maneira em qualquer idioma que estiver usando e depois ajudar a pessoa de lá a entender o que está acontecendo, se necessário.