Ahora, implementaremos un el algoritmo quicksort para ordenar listas y lo haremos en F# y C# para compararlos.
Para el que no conoce el algoritmo quicksort, vamos a ver la lógica:
Si la lista está vacía, no hay nada que hacer.
De otra manera:
- Tome el primer elemento de la lista, que lo llamaremos pivot
- Buscamos todos los elementos menores al pivot y los ordenamos usando el algoritmo quicksort.
- Buscamos todos los elementos mayores al pivot y los ordenamos usando el algoritmo quicksort.
- Combinamos las tres partes para obtener el resultado final: (elementos menores + pivot + elementos mayores)
Tenga en cuenta que hemos simplificado este algoritmo para hacer la explicación más simple.
Veamos el código en F#:
let rec quicksort list =
match list with
| [] -> // Si la lista es vacia
[] // retorna una lista vacia
| firstElem::otherElements -> // si no es vacia
let smallerElements = // toma los menores
otherElements
|> List.filter (fun e -> e < firstElem)
|> quicksort // y los ordena
let largerElements = // toma los mayores
otherElements
|> List.filter (fun e -> e >= firstElem)
|> quicksort // y los ordena
// concatena estas 3 partes y la retorna.
List.concat [smallerElements; [firstElem]; largerElements]
//test
printfn "%A" (quicksort [1;5;23;18;9;1;3])
Repasemos el código:
No hay declaraciones de tipos en ningún lado. Esta función funcionará en cualquier lista que tenga elementos comparables (que es casi todos los tipos F#, ya que automáticamente tienen una función de comparación predeterminada).
Toda la función es recursiva: esto se señala al compilador utilizando la palabra clave rec en "let rec quicksort list =".
Con match..with se esta usando pattern matching, las expresiones son como esta:
match x with
| caseA -> something
| caseB -> somethingElse
El pattern matching es una técnica que analiza objetos y ejecuta el código que corresponde (cuando el objeto aplica le patron)
De esta manera se pregunta si la lista es vacía, y si es vacía se retorna una lista vacía.
De lo contrario, aplica la lógica descrita anteriormente. Es decir filtra la lista de los menores por medio de una función anónima que se pasa como clausura, que indica como se va a filtrar y luego se ordena utilizando quicksort, luego filtra la lista de los mayores y los ordena . Y por ultimo se retorna la concatenación de estas 3 partes. ,
Veamos la implementación en C# sin LinQ :
public class QuickSortHelper
{
public static List<T> QuickSort<T>(List<T> values)
where T : IComparable
{
if (values.Count == 0)
{
return new List<T>();
}
// Tomamos el primer valor
T firstElement = values[0];
// Filtramos los elementos
var smallerElements = new List<T>();
var largerElements = new List<T>();
for (int i = 1; i < values.Count; i++) {
var elem = values[i];
if (elem.CompareTo(firstElement) < 0)
{
smallerElements.Add(elem);
}
else
{
largerElements.Add(elem);
}
}
result.AddRange(QuickSort(smallerElements.ToList()));
result.Add(firstElement);
result.AddRange(QuickSort(largerElements.ToList()));
return result;
}
}
Comparando los dos programas, nuevamente podemos ver que el código F# es mucho más compacto, con menos ruido y sin necesidad de declaraciones de tipo.
Además, el código F# se lee casi exactamente como es algoritmo, a diferencia del código C#. Esta es otra ventaja clave de F# - el código es generalmente más declarativo ("qué hacer") y menos imperativo ("cómo hacerlo") que C#, y por lo tanto es mucho más autodocumentado.
Veamos una versión más funcional en C#:
public static class QuickSortExtension
{
public static IEnumerable<T> QuickSort<T>(
this IEnumerable<T> values) where T : IComparable
{
if (values == null || !values.Any())
{
return new List<T>();
}
var rest = values.Skip(1);
.Where(i => i.CompareTo(firstElement) < 0)
.QuickSort();
var largerElements = rest
.Where(i => i.CompareTo(firstElement) >= 0)
.QuickSort();
return smallerElements
.Concat(new List<T>{firstElement})
.Concat(largerElements);
}
}
Esto es mucho más limpio, y lee casi lo mismo que la versión F#.
Finalmente, el código F# a menudo funciona la primera vez, mientras que el código C# puede requerir más depuración.
Pero incluso la ultima versión funcional C# tiene inconvenientes en comparación con la versión F#. Por ejemplo, como F# usa la coincidencia de patrones, no es posible derivar al caso de la "lista no vacía" con una lista vacía.
Dejo link: https://fsharpforfunandprofit.com/posts/fvsc-quicksort/
No hay declaraciones de tipos en ningún lado. Esta función funcionará en cualquier lista que tenga elementos comparables (que es casi todos los tipos F#, ya que automáticamente tienen una función de comparación predeterminada).
Toda la función es recursiva: esto se señala al compilador utilizando la palabra clave rec en "let rec quicksort list =".
Con match..with se esta usando pattern matching, las expresiones son como esta:
match x with
| caseA -> something
| caseB -> somethingElse
El pattern matching es una técnica que analiza objetos y ejecuta el código que corresponde (cuando el objeto aplica le patron)
De esta manera se pregunta si la lista es vacía, y si es vacía se retorna una lista vacía.
De lo contrario, aplica la lógica descrita anteriormente. Es decir filtra la lista de los menores por medio de una función anónima que se pasa como clausura, que indica como se va a filtrar y luego se ordena utilizando quicksort, luego filtra la lista de los mayores y los ordena . Y por ultimo se retorna la concatenación de estas 3 partes. ,
Veamos la implementación en C# sin LinQ :
public class QuickSortHelper
{
public static List<T> QuickSort<T>(List<T> values)
where T : IComparable
{
if (values.Count == 0)
{
return new List<T>();
}
// Tomamos el primer valor
T firstElement = values[0];
// Filtramos los elementos
var smallerElements = new List<T>();
var largerElements = new List<T>();
for (int i = 1; i < values.Count; i++) {
var elem = values[i];
if (elem.CompareTo(firstElement) < 0)
{
smallerElements.Add(elem);
}
else
{
largerElements.Add(elem);
}
}
result.AddRange(QuickSort(smallerElements.ToList()));
result.Add(firstElement);
result.AddRange(QuickSort(largerElements.ToList()));
return result;
}
}
Comparando los dos programas, nuevamente podemos ver que el código F# es mucho más compacto, con menos ruido y sin necesidad de declaraciones de tipo.
Además, el código F# se lee casi exactamente como es algoritmo, a diferencia del código C#. Esta es otra ventaja clave de F# - el código es generalmente más declarativo ("qué hacer") y menos imperativo ("cómo hacerlo") que C#, y por lo tanto es mucho más autodocumentado.
public static class QuickSortExtension
{
public static IEnumerable<T> QuickSort<T>(
this IEnumerable<T> values) where T : IComparable
{
if (values == null || !values.Any())
{
return new List<T>();
}
var rest = values.Skip(1);
.Where(i => i.CompareTo(firstElement) < 0)
.QuickSort();
var largerElements = rest
.Where(i => i.CompareTo(firstElement) >= 0)
.QuickSort();
return smallerElements
.Concat(new List<T>{firstElement})
.Concat(largerElements);
}
}
Esto es mucho más limpio, y lee casi lo mismo que la versión F#.
Finalmente, el código F# a menudo funciona la primera vez, mientras que el código C# puede requerir más depuración.
Pero incluso la ultima versión funcional C# tiene inconvenientes en comparación con la versión F#. Por ejemplo, como F# usa la coincidencia de patrones, no es posible derivar al caso de la "lista no vacía" con una lista vacía.
Dejo link: https://fsharpforfunandprofit.com/posts/fvsc-quicksort/
