Por maior procedimentos de ordem?

Question

Assim, se uma linguagem fornece procedimento de ordem superior, em seguida, eu posso ter procedimento que procedimento retorna. Algo como:

(define (Proc a b c)
  (lambda (x) ( #| method body here in terms of a b c and x |# )))

Para criar novo procedimento, gostaria apenas de fazer algo como:

(define ProcA (Proc a1 b1 c1)) ; Would create ProcA that has 1 argument

tarefa semelhante poderia ser feito em um idioma que não suporta procedimento de ordem superior, definindo Proc que leva de 4 em vez de 3 argumentos e chamando este procedimento para definir ProcA, como:

(define (Proc a b c x) ( #| method body -- does not return any procedure |# )
(define (ProcA x) (Proc a1 b1 c1 x))

Então, por que há tanta fuzz sobre o procedimento de ordem superior? Estou faltando alguma coisa?

Answer 1

É uma boa observação de que uma função que retorna outra função é o mesmo que uma função que leva dois argumentos. Isso é chamado de "Currying". Dito de outra forma, uma função de A para B é a prova de uma implicação lógica, que A implica B, ou:

A => B.

Como você note, se A implica que B implica C, então A e B implica C, ou:

(A => (B => C)) <==> ((A, B) => C)

Mas uma função de ordem superior não é necessariamente uma função que retorna outra função. Função A de ordem superior é uma função que leva uma outra função como seu argumento . Esta é uma diferença importante, e Hofs são imensamente poderosas ferramentas de programação.

Por exemplo, considere esta função Haskell:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : (map f xs)

Esta função de ordem superior tem uma função f eo aplica a todos os elementos em uma lista. Em linguagens sem Hofs, você faria o que esta função faz com um loop ou algo semelhante, mas em uma língua que tem Hofs, você pode chamar f para cada elemento da lista com uma chamada simples como isto:

map f myList

Claro, construções de controle em línguas deixá-lo aproximar funções de ordem superior, mas uma linguagem que tem funções de ordem superior permite que você inventar o seu próprio controle de construções . Esquema certamente se qualifica.

Answer 2

Eu não vou tentar recapitular o argumento aqui, mas em Por Matters programação funcional , John Hughes argumenta que as funções de ordem superior são úteis porque são formas mais eficazes para "unir" partes de um programa, e, assim, eles tornam mais fácil a reutilização de código. Os exemplos estão em um idioma muito antigo que já não é muito usado, mas eles ainda são fáceis de seguir e muito convincente. papel da leitura John é uma boa maneira de obter uma resposta detalhada à pergunta "por que há tanta fuzz sobre os procedimentos de ordem superior".

Answer 3

Este é mais sobre a mentalidade de viabilidade. Ele permite que você funções tratar como cidadãos de primeira classe e pensar em termos de funções que operam em funções para criar outras funções, etc.

Obviamente você poderia fazer ou simular isso com outras línguas, mas se não é um mecanismo sintático é uma espécie de tratado como uma adição ou um hack.

Answer 4

OK, mas no segundo exemplo, você está criando esse procedimento em tempo de compilação com uma lista pré-ordenada por a1, b1 e c1. No primeiro exemplo, você está criando-lo em tempo de execução quando você chamar ProcA, e você pode criar como muitos diferentes como quiser, para que você pode fazer coisas muito mais interessantes.

Answer 5

Pense em uma função de transformação ou de um algoritmo de ordenação através de um array. Agora, você quer torná-la realmente flexível para permitir que o usuário de sua função para especificar o comportamento de sua função por deixá-los passar uma função como um argumento.

Diga, você escrever um algoritmo de ordenação com o seguinte protótipo de procedimento:

sort(Array a, void (*fn)(a::element_type, a::element_type));

O usuário de que a função poderia especificar, passando o fn apropriado, se eles querem um descendente ou ascendente ordenação.

Answer 6

Você precisaria de uma classe interna para simular adequadamente isso. O primeiro caso, Proc é fechada sobre a, b e c. No segundo caso, o chamador de proca não pode controlar a a1, b1 e c1 são passados ??para o outro procedimento, ele só pode controlar x. Então, a maneira como você controlar a1, b1 e c1 são através das variáveis ??de uso em um escopo (nível de módulo ou algo assim) mais elevado, o que torna a sua função não puro. Nesse caso, você não pode garantir que recebe os mesmos argumentos entre as chamadas, Proca retornará o mesmo resultado. Onde como com Proc, você sempre pode ter certeza que se você chamá-lo com os mesmos argumentos, os mesmos resultados vai acontecer.

Answer 7

Eu uso funções de ordem superior em javascript, por exemplo, quando eu uso uma caixa de seleção. Eu posso passar na função que será chamada quando uma opção é selecionada, como a única diferença para mim foi que, o que simplifica o meu código, ele reduz a redundância.

Eu vejo a mesma coisa em outras línguas que eu uso que os suportes de ordem superior funções, como eu pode, então, começar a olhar para como limpar o meu código, onde existe alguma redundância que pode ser localizada, e quaisquer diferenças podem ser feito em uma função.

Uma vez que C # suportado isso, eu sabia que era agora mais mainstream. :)

Answer 8

Se a função aceita e / ou retorna uma função, ela é chamada uma função de ordem superior (HOF). Para os programadores inexperientes, vindos de C, C ++ ou Java, funções de ordem superior parecer mágica, mas eles são muito simples. Imagine uma função simples que retorna o resultado de 2 + 3:

(define (foo) (+ 2 3)) ;; (foo) => 5

Isso é uma função chato, ele sempre adiciona 2 a 3. E se generalizá-lo, para que ele adiciona 2 não só a 3, mas para qualquer número fornecido pelo usuário?

(define (foo n) (+ 2 n)) ;; (foo 10) => 12

Quando um idioma não suporta funções de ordem superior, você é forçado a pensar que as funções e valores (por exemplo, números, booleanos, listas) são 2 coisas distintas. Mas programação funcional (FP) borrões distinção entre eles. Imagine que a única diferença entre uma função e um valor é que a função pode ser chamada, diferente do que você pode fazer para uma função de tudo o que você poderia a um 2 ou #t ou '(a b c): você poderia dar-lhe como um argumento, ou o retorno de uma função, ou armazenar em uma variável, ou colocá-lo em uma lista. Por exemplo, vamos generalizar nossa função pouco mais, por isso não só pode adicionar 2 a n, mas multiplicar 2 por n, ou aplicar qualquer outra função que aceitaria dois números:

(define (foo f n) (f 2 n))
;; (foo + 10) => 12
;; (foo * 10) => 20
;; (foo expt 10) => 1024

Quando você percebe que uma função pode ser tratado da mesma maneira que um número ou uma string é tratado, anônimo funções (chamados de “lambdas” em FP jargão) faz todo o sentido. funções anônimas são realmente mais básico e “normal” do que comuns funções nomeados, funções nomeadas são funções apenas anônimos colocar em uma variável, assim como nós colocar um número em uma variável de usá-lo várias vezes.

(+ 2 2) ;; is no different from:
(let ((a 2)) (+ a a))
(lambda (x y) (* x y)) ;; is no different from:
(define (foo x y) (* x y)) ;; which is an abbreviation for:
(define foo (lambda (x y) (* x y))).

Assim Hofs nos permite generalizar as nossas funções para torná-los super-flexível. Se você olhar para a sua função, ver a lógica por trás disso, você pode perceber que, se algo opera em seus dados, então outra coisa poderia provavelmente também. Se você adicionar 2 números juntos, você provavelmente poderia multiplicá-los, ou subtrair, ou exponentiate um para outro, ou o que quer. Em vez de escrever uma nova função para cada caso de cada vez, você poderia simplesmente aceitar um parâmetro adicional, que tem de ser uma função.

Em FP usamos Hofs todas as listas do tempo, por exemplo, quando manipulando. 3 funções são o pão e manteiga da FP: map , filter e foldl . map aceita uma função com um argumento, aplica-se esta função para cada elemento de uma lista, e retorna uma nova lista com elementos alterados. filter aceita um predicado (função que retorna um booleano) com 1 argumento, aplica-se o predicado a cada elemento de uma lista, e retorna uma nova lista com elementos que não satisfazem o predicado removida.

(map (lambda (n) (+ n 1)) '(1 2 3 4 5) ;; '(2 3 4 5 6)
(define (foo n) (+ n 1))
(map foo '(1 2 3 4 5)) ;; '(2 3 4 5 6)
(filter (lambda (n) (> n 3)) '(1 2 3 4 5)) ;; '(4 5)
(define (bar n) (> n 3))
(filter bar '(1 2 3 4 5)) ;; '(4 5)

Imagine, você tem uma lista de 1-arity funções de novo, você pode fazer o que quiser com uma função, e armazená-lo em uma estrutura de dados também e você deseja aplicar todos eles para o mesmo número, e obter uma lista de resultados.

(let ((xs (list (lambda (x) (+ x 1))
                (lambda (x) (* x 2))
                (lambda (x) (- x)))))
  (map (lambda (f) (f 10)) xs)) ;; => (11 20 -10)

Conclusão: quando uma linguagem de programação suporta adequadamente conceitos de programação funcional, funções de ordem superior permitem flexibilidade e generalidade, o que torna seu código tanto mais poderoso (você pode usar a mesma função para vários casos de uso) e conciso (não há necessidade de escrever 10 versões de uma função). Algumas funções de ordem superior são muito usados ??na programação funcional, de modo a se livrar de baixo nível e detalhado para-loops e gravação one-liners que fazem tudo em seu lugar.

Nota: foldl, que é o mesmo que “esquerda dobrar” ou “esquerda reduzir”, é ainda mais poderoso. Se você estiver realmente interessado e tiver tempo, leia o primeiro semestre de minha resposta usando reduzir . Enquanto ele não é escrito para Esquema / Racket, mas em vez de Common Lisp / Emacs Lisp, você ainda pode entender a idéia por trás dobrar / reduzir.