Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 11 sur 11
  1. #1
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 563
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 563
    Points : 5 993
    Points
    5 993

    Par défaut Incompréhension sur les types

    Bonjour

    je me lance dans le F# avec Visual 2010 et je bute sur une difficulté :
    J'ai ecrit une fonction merge qui est censée fusionner deux séquences :
    Code :
    1
    2
    3
    4
    5
    6
    let rec merge x y =
        if Seq.isEmpty(x) then y
        elif Seq.isEmpty(y) = 0 then x
        elif Seq.head(x) < Seq.head(y) then Seq.append (Seq.head(x)) (merge (Seq.skip 1 x) y)
        elif Seq.head(x) > Seq.head(y) then Seq.append (Seq.head(y)) (merge x (Seq.skip 1 y))
        else Seq.append (Seq.head(x))  (merge (Seq.skip 1 x) (Seq.skip 1 y))
    Lorsque je lance le test
    Code :
    1
    2
    3
    4
    let s1 = {1..3}
    let s2 = {2..6}
    
    printfn "%A" (merge s1 s2)
    J'ai l'erreur suivante : erreur FS0001: Le type 'int' n'est pas compatible avec le type 'seq<int>' en me désignant s1. Où est mon erreur ?

    Merci
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  2. #2
    LLB
    LLB est déconnecté
    Membre Expert
    Inscrit en
    mars 2002
    Messages
    962
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 962
    Points : 1 263
    Points
    1 263

    Par défaut

    Le type de ta fonction merge est :
    Code :
    1
    2
    val merge :
      seq<'a> -> seq<'a> -> seq<'a> when 'a : comparison and 'a :> seq<'a>
    Cela indique que les éléments de ton seq doivent être eux-mêmes des seq. Cela explique donc l'erreur quand tu appelles "merge s1 s2".

    La raison est que Seq.append prend un seq en premier argument. Or, tu lui donnes le premier élément de x ou y. Une correction rapide :

    Code :
    1
    2
    3
    4
    5
    6
    let rec merge x y =
        if Seq.isEmpty(x) then y
        elif Seq.isEmpty(y) then x
        elif Seq.head(x) < Seq.head(y) then Seq.append [Seq.head(x)] (merge (Seq.skip 1 x) y)
        elif Seq.head(x) > Seq.head(y) then Seq.append [Seq.head(y)] (merge x (Seq.skip 1 y))
        else Seq.append [Seq.head(x)]  (merge (Seq.skip 1 x) (Seq.skip 1 y))
    Cependant, ce genre de code est déconseillé : parcourir et reconstruire une séquence est coûteux (ce ne sont pas des listes). À lire ton code, je pense deviner que tu souhaiterais utiliser des ensembles plutôt (set). Je te propose ceci :

    Code :
    1
    2
    3
    4
    5
    let s1 = set {1..3}
    let s2 = set {2..6}
    let union = s1 + s2
    
    val union : Set<int> = set [1; 2; 3; 4; 5; 6]

  3. #3
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 563
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 563
    Points : 5 993
    Points
    5 993

    Par défaut

    Merci pour ta réponse. Ça fonctionne bien mieux maintenant, je soupsonnais un truc comme ça mais comme c'était une séquence je mettais des accolades précédées de seq au lieu de crochets et évidemment ça ne compilait pas.
    Ce que je veux faire c'est essayer de transcrire ce code Haskell, qui calcule les nombres de Hamming en F# :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
         where merge (x:xs) (y:ys)
                | x < y = x : xs `merge` (y:ys)
                | x > y = y : (x:xs) `merge` ys
                | otherwise = x : xs `merge` ys
     
    main = do
        print $ take 20 hamming
        print $ hamming !! 1690
        print $ hamming !! 999999
    Je l' ai transcrit avec des listes mais ça plante assez vite par stack overflow. Je me disais qu'en utilisant la "paresse" des séquences ça pourrait peut-être marcher. Ça me permettra au moins de comprendre comment la paresse fonctionne.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  4. #4
    LLB
    LLB est déconnecté
    Membre Expert
    Inscrit en
    mars 2002
    Messages
    962
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 962
    Points : 1 263
    Points
    1 263

    Par défaut

    C'est un code vraiment pensé en Haskell.

    Si tu peux laisser la paresse de côté et calculer les nombres jusqu'à n, tu peux faire ça :
    Code :
    1
    2
    3
    4
    5
    6
    7
    let hamming n =
      [ yield 1
        yield! List.map ((*)2) [1..n/2]
        yield! List.map ((*)3) [1..n/3]
        yield! List.map ((*)5) [1..n/5]
      ]
      |> Seq.distinct |> Seq.sort
    Ce n'est peut-être pas le plus efficace, mais hamming 2000000 (qui renvoie 1466667 nombres) prend 1,3 secondes chez moi.

    En général, seq est utile quand on veut de la paresse. On utilise les fonctions du module Seq pour itérer ou combiner. Pour ta fonction, je n'ai pas trouvé de façon simple de faire, on pourrait écrire notre propre itérateur, mais ce n'est pas super pratique.

    Dans ton cas, je te conseille d'utiliser les LazyList du PowerPack (#r "FSharp.Powerpack.dll"), tu devrais obtenir à peu près la même chose qu'en Haskell :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    module LL = LazyList
    let rec merge x y =
        match x, y with
        | LL.Cons(e1, xs), LL.Cons(e2, ys) when e1 < e2 -> LL.cons e1 (merge xs y)
        | LL.Cons(e1, xs), LL.Cons(e2, ys) when e1 > e2 -> LL.cons e2 (merge x ys)
        | LL.Cons(e1, xs), LL.Cons(e2, ys) -> LL.cons e1 (merge xs ys)
        | LL.Nil, _ -> y
        | _, LL.Nil -> x

  5. #5
    LLB
    LLB est déconnecté
    Membre Expert
    Inscrit en
    mars 2002
    Messages
    962
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 962
    Points : 1 263
    Points
    1 263

    Par défaut

    Pour éviter le stackoverflow avec les LazyList, il faut utiliser consDelayed de temps en temps.

    Le code complet :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    module LL = LazyList
    let rec merge x y =
        match x, y with
        | LL.Cons(e1, xs), LL.Cons(e2, ys) when e1 < e2 ->
            LL.consDelayed e1 (fun _ -> merge xs y)
        | LL.Cons(e1, xs), LL.Cons(e2, ys) when e1 > e2 ->
            LL.cons e2 (merge x ys)
        | LL.Cons(e1, xs), LL.Cons(e2, ys) -> LL.cons e1 (merge xs ys)
        | LL.Nil, _ -> y
        | _, LL.Nil -> x
    
    let hamming =
        let numbers = Seq.initInfinite ((+)1) |> LL.ofSeq
        LL.map ((*) 2) numbers
        |> merge (LL.map ((*) 3) numbers)
        |> merge (LL.map ((*) 5) numbers)
    C'est un peu plus lent que la version non paresseuse, mais une fois qu'on a accédé à un élément, c'est presque instantané si on le demande à nouveau.

  6. #6
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 563
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 563
    Points : 5 993
    Points
    5 993

    Par défaut

    Ton premier code ne calcule pas les nombres de Hamming qui sont uniquement des multiples de 2 3 et 5, la liste [1..n/2] introduit des nombres incorrects (7 11 ...).
    D'autre part, je ne peux pas compiler cette ligne module LL = LazyList, peut-être dois-je faire un open de quelque chose.
    [EDIT] je viens de voir qu'il faut ajouter le powerPack, comment on fait ???[/EDIT]
    [EDIT bis]Problème réglé [/EDIT bis]
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  7. #7
    LLB
    LLB est déconnecté
    Membre Expert
    Inscrit en
    mars 2002
    Messages
    962
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 962
    Points : 1 263
    Points
    1 263

    Par défaut

    Dans le premier code, le map sert justement à obtenir les multiples.

    Code :
    1
    2
    3
    4
    > hamming 50 |> Seq.toList;;
    val it : int list =
      [1; 2; 3; 4; 5; 6; 8; 9; 10; 12; 14; 15; 16; 18; 20; 21; 22; 24; 25; 26; 27;
       28; 30; 32; 33; 34; 35; 36; 38; 39; 40; 42; 44; 45; 46; 48; 50]
    C'est pas bon ?


    Je laisse le lien du powerpack (ça servira à d'autres) : http://fsharppowerpack.codeplex.com

  8. #8
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 563
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 563
    Points : 5 993
    Points
    5 993

    Par défaut

    Non, c'est pour ça que je faisais une récursion à partir de la liste initiale [1], les résultats sont :
    Les 20 premiers nombres :
    1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
    le 1691 ieme
    2125764000
    le millionième
    519312780448388736089589843750000000000000000000000000000000000000000000000000000000
    A noter qu'en Prolog j'arrive à le faire mais avec un autre algo, et c'est évidemment plus lent

    Pour le powerPack, il faut ajouter la référence dans le projet (en plus du téléchargement de la dll)
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  9. #9
    LLB
    LLB est déconnecté
    Membre Expert
    Inscrit en
    mars 2002
    Messages
    962
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 962
    Points : 1 263
    Points
    1 263

    Par défaut

    OK, en ajoutant la récursion :
    Code :
    1
    2
    3
    4
    5
    let rec hamming = LL.consDelayed 1I (fun() ->
        let l2 = LL.map ((*)2I) hamming
        let l3 = LL.map ((*)3I) hamming
        let l5 = LL.map ((*)5I) hamming
        merge (merge l2 l3) l5)
    Je trouve bien les mêmes résultats que toi, le millionième est calculé en 6,5s.

  10. #10
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 563
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 563
    Points : 5 993
    Points
    5 993

    Par défaut

    J'arrive a un stackoverflow avec ça dès hamming 24 !!!
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    module LL = LazyList
    let rec merge x y =
        match x, y with
        | LL.Cons(e1, xs), LL.Cons(e2, ys) when e1 < e2 ->
            LL.consDelayed e1 (fun _ -> merge xs y)
        | LL.Cons(e1, xs), LL.Cons(e2, ys) when e1 > e2 ->
            LL.cons e2 (merge x ys)
        | LL.Cons(e1, xs), LL.Cons(e2, ys) -> LL.cons e1 (merge xs ys)
        | LL.Nil, _ -> y
        | _, LL.Nil -> x
    
    
    let hamming a =
        let rec loop a ham acc2 acc3 acc5 = 
            if (a = 1) then ham
            else 
                let tmp = merge ham (merge acc2 (merge acc3  acc5))
                loop (a - 1) tmp (LL.map (fun x -> 2I*x) tmp) (LL.map (fun x -> 3I*x) tmp) (LL.map (fun x -> 5I*x) tmp)
           LL.take a (loop a (LL.ofList([1I])) LL.empty LL.empty LL.empty)
    
    let ham = hamming 24
    
    printfn "%A" (List.head(List.rev(LL.toList ham )))
    Je vais me plonger dans les initialisations !
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  11. #11
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 563
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 563
    Points : 5 993
    Points
    5 993

    Par défaut

    Nos messages se sont croisés, effectivement tout est une question d'initialisation !
    Merci
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •