Haskell - Aide à la programmation fonctionnelle

Question

Essayer de ressentir le haschell. Suis un programmeur chevronné avec PHP, JAVA, VB et beaucoup d'autres langues, mais je trouve haskell un peu plus difficile à suivre. Quelqu'un peut-il me donner une traduction pour la fonction haskell suivante, pour me lance ...

quicksort []  = [] 
quicksort (x:xs) = quicksort [y | y <- xs, y<x ] 
        ++ [x] 
        ++ quicksort [y | y <- xs, y>=x] 

Un exemple de traduction anglaise est dans les commentaires ci-dessous:

// --- FOR_LOOP -> 
// --- $abc goes from 1 to 10 -> 
// --- If $abc is even - print $abc is even -> 
// --- else if $abc is odd - print $abc is odd -> 
// --- END_FOR_LOOP 

for($abc = 1 ; $abc <= 10 ; $abc++){ 

    if($abc % 2 == 0){ 
    echo $abc . " is even"; 
    } 
    else{ 
    echo $abc . " is odd"; 
    } 
} 

La première ligne est assez simple, en lisant: "La fonction quicksort sur une liste vide donne comme résultat une liste vide" ... Si vous pouvez traduire le reste du haskell en anglais t Le chapeau serait très utile.

Answer 1

Le résultat de quicksorting la liste vide est la liste vide.

Le résultat de quicksorting une liste non vide, où l'on appelle le premier élément de la liste x et les autres éléments xs est: Le résultat de quicksorting tous les éléments de xs qui sont plus petits que x (*), suivi par x, suivi du résultat de quicksorting tous les éléments de xs supérieurs à x.

(*) Pour élaborer un peu: [y | y <- xs, y<x ] peut être lu comme "la liste de tous y où y est en xs et y<x".

Answer 2

Cela ne répond pas directement à votre question, mais hoogle peut aider votre apprentissage en général, vous pouvez l'utiliser pour rechercher les bibliothèques d'API standard par le nom de la fonction, ou par la signature de type approximatif.

est ici des exemples des termes de recherche qu'il soutient:

map 
(a -> b) -> [a] -> [b]` 
Ord a => [a] -> [a] 
Data.Map.insert 

Answer 3

ont pas fait depuis le collège ...

Il est récursive - la première ligne est le cas pour un ensemble vide.

quicksort []  = [] 

Les lignes suivantes fonctionnent sur un ensemble non vide. La syntaxe (x: xs) la divise en un seul élément (x) et les éléments restants (xs).

quicksort (x:xs) = quicksort [y | y <- xs, y<x ] 
    ++ [x] 
    ++ quicksort [y | y <- xs, y>=x] 

La première ligne, quicksort [y | y < - xs, y < x], appelle quicksort contre l'ensemble de tous les éléments de xs inférieur à x (c'est-à-dire chaque y de xs inférieur à x). Si xs est l'ensemble vide, alors quicksort [] retournera [].

La ligne médiane est simplement l'ensemble contenant x.

La dernière ligne, quicksort [y | y < - xs, y > = x], appelle quicksort contre l'ensemble de tous les éléments de xs qui sont supérieurs ou égaux à x (c'est-à-dire chaque y de xs supérieur ou égal à x). Si xs est l'ensemble vide, alors quicksort [] retournera [].

Le résultat final est un ensemble ordonné.

Answer 4

C'est un langage déclaratif, donc vous venez de lire ce que vous voyez. sepp2k fait un bon exemple ci-dessus.

Answer 5

Vérifiez le http://learnyouahaskell.com/recursion#quick-sort, il explique exactement ce que fait le quicksort.

Answer 6

Dans le cas où votre problème est en familiarité avec compréhensions de liste, voici quelques versions alternatives qui sont plus ou moins le même:

quicksort []  = [] 
quicksort (x:xs) = 
    quicksort (filter (< x) xs) ++ 
    [x] ++ 
    quicksort (filter (>= x) xs) 

quicksort []  = [] 
quicksort (x:xs) = 
    quicksort smaller ++ [x] ++ quicksort bigger 
    where 
    (smaller, bigger) = partition (< x) xs