No quieres saber.
¿Qué? ¿Tú lo haces? ¿Estás seguro?
Okay.
En primer lugar, depende de cómo defina “clasificación rápida”. Algunas personas usan el término para referirse solo al algoritmo de dividir y conquistar que clasifica una secuencia de valores, pero otras personas lo usan para referirse a una implementación de ese algoritmo para la clasificación in situ de una secuencia de celdas mutables que contienen valores.
- ¿Qué es una cola prioritaria?
- ¿Cuál es la mejor manera de aprender estructuras de datos y algoritmos para estudiantes que no son de CS / IT?
- Dado un gráfico bipartito, ¿cómo puedo encontrar su subgrafo que es un gráfico bipartito completo y tiene la mayor cantidad de vértices?
- Cómo escribir un código para fusionar dos listas vinculadas ordenadas
- ¿Cómo es la búsqueda tan rápida por los motores de búsqueda? Generan millones de instrucciones en menos de un segundo. ¿Qué algoritmo usan?
Si acepta la primera definición, se puede implementar un algoritmo de clasificación rápida que clasifica una secuencia de números naturales en el cálculo lambda sin tipo utilizando la codificación de la iglesia para los naturales, los booleanos y la secuencia misma.
Por otro lado, si solo acepta la segunda definición, tenemos un problema: el cálculo lambda sin tipo no tiene noción de “célula mutable”, por lo tanto, no es directamente implementable en el sentido de que la definición del segundo algoritmo no tiene ningún sentido en el contexto del cálculo.
Sin embargo, si desea enriquecer el cálculo con algún tipo de noción definida externamente (al cálculo mismo) de acceso y mutación de una secuencia de células mutables (indexadas por números naturales codificados por la iglesia expresados en el cálculo lambda), y con operadores correspondientes a composición monádica para esas primitivas en el contexto del cálculo lambda, entonces puede expresar el cálculo monádico que clasifica la secuencia de células usando el cálculo lambda mismo.
¿Suena confuso? Bueno, olvidémonos de las cosas monádicas y aceptemos la primera definición: clasificación rápida como el algoritmo de dividir y conquistar para ordenar una secuencia de valores (no una secuencia de celdas mutables que contengan valores).
Luego, como escribí, es solo un trabajo preliminar codificarlo usando números codificados de iglesia, booleanos y secuencias.
Pero aún no desea ver la expresión lambda resultante.
¿Qué? ¿Tú lo haces? ¿Estás seguro?
Okay.
Aquí hay una forma de codificarlo:
(λf. (λx.f (xx)) (λx.f (xx))) (λf.λl.l (λx.λc.x) (λh.λt.LCat (f (((λf. (λx.f (xx)) (λx.f (xx))) (λf.λp.λl.l (λx.λc.x) (λh.λt. ((ph) ((λh.λt.λx.λc.cht) h ) (λx.x)) (fpt)))) (((λf.λx.λy.fyx) (λm.λn. (λn.n (λf.λt.λf.f) (λt.λf.t)) ((λm.λn. (n (λn.λf.λx.n (λg.λh.h (gf)) (λc.x) (λx.x))) m) mn))) h) t)) ( (λh.λt.λx.λc.cht) h (f (((λf. (λx.f (xx)) (λx.f (xx))) (λf.λp.λl.l (λx.λc.x ) (λh.λt. ((ph) ((λh.λt.λx.λc.cht) h) (λx.x)) (fpt)))) ((((λf.λx.λy.fyx) (λm. λn. (λb.b (λt.λf.f) (λt.λf.t)) ((λm.λn. (λn.n (λf.λt.λf.f) (λt.λf.t)) (( λm.λn. (n (λn.λf.λx.n (λg.λh.h (gf)) (λc.x) (λx.x))) m) mn)) mn))) h) t)) )))
(esperando no haber estropeado nada)
Mmm, ok. No es bonito y básicamente ilegible.
Expresémoslo en términos de combinadores y agreguemos una pequeña sangría y alineación aquí y allá:
Y = λf. (Λx.f (xx)) (λx.f (xx))
Id = λx.x
Flip = λf.λx.λy.fyx
Verdadero = λt.λf.t
Falso = λt.λf.f
No = λb.b Falso Verdadero
Cero = λf.λx.x
Succ = λn.λf.λx.f (nfx)
Pred = λn.λf.λx.n (λg.λh.h (gf)) (λc.x) Id
Menos = λm.λn. (n Pred) m
IsZero = λn.n (λf.False) Verdadero
LessEq = λm.λn.IsZero (Menos mn)
Greatr = λm.λn.Not (LessEq mn)
Nulo = λx.λc.x
Contras = λh.λt.λx.λc.cht
FLCat = λf.λx.λy.xy (λh.λt.Cons h (fty))
LCat = Y FLCat
FFlter = λf.λp.λl.l Nil (λh.λt. ((Ph) (Cons h) Id) (fpt))
Filtro = Y FFltro
FQSort = λf.λl.l Nil
(λh.λt.LCat (f (Filtro ((Flip LessEq) h) t))
(Cons h (f (Filtro ((Flip Greatr) h) t))))
QSort = Y FQSort
¿Eso está mejor?
