Incompréhension sur les types [Résolu]

[Trap D]

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

[LLB]

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]

[Trap D]

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.

[LLB]

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

[LLB]

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.

[Trap D]

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]

[LLB]

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

[Trap D]

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)

[LLB]

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.

[Trap D]

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 !

[Trap D]

Nos messages se sont croisés, effectivement tout est une question d'initialisation !
Merci