Back to Questions
1.4k
views8
comments
Compiler bugs?
f#compiler

Hello.

I convert a list of lists in a tree.

But get errors in 3 and 4 tests. How do you comment on them? This compiler bugs?

Source: [link:pastebin.org]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#nowarn "40"

let flip f a b = f b a
let curry f a b = f (a, b)
let uncurry f (a, b) = f a b

type Tree<'a> = Node of 'a * Tree<'a> list

let testData = [[1; 2; 3]; [1; 2; 4]; [1; 2; 3; 5]]

//-----------------------------------------------------------------------------------

let test1 () = // OK
    let rec yoba1 = Seq.filter ((<>) [])
                 >> Seq.groupBy List.head
                 >> Seq.sortBy fst
                 >> Seq.map (fun (key, values) -> Node (key, yoba1 (Seq.map List.tail values)))
                 >> Seq.toList

    testData |> yoba1 |> printfn "test1: %A"

//-----------------------------------------------------------------------------------

let test2 () = // OK
    let rec yoba2 = Seq.filter ((<>) [])
                 >> Seq.groupBy List.head
                 >> Seq.sortBy fst
                 >> Seq.map (uncurry (flip (Seq.map List.tail
                                         >> fun values -> yoba2 values
                                         >> fun nextNodes -> fun key -> Node (key, nextNodes))))
                 >> Seq.toList

    

    testData |> yoba2 |> printfn "test2: %A"

//-----------------------------------------------------------------------------------

//let test3 () = // PHAIL - Not compile. The compiler believes that this self-expression, such as "let rec x = x + 1"
//    
//    let rec yoba3 = Seq.filter ((<>) [])
//                 >> Seq.groupBy List.head
//                 >> Seq.sortBy fst
//                 >> Seq.map (uncurry (flip (Seq.map List.tail
//                                         >> yoba3 // Minimized ">> fun values -> yoba3 values"
//                                         >> fun nextNodes -> fun key -> Node (key, nextNodes))))
//                 >> Seq.toList
//    
//    testData |> yoba3 |> printfn "test3: %A"

//-----------------------------------------------------------------------------------

test1 ()
test2 ()
//test3 ()
// test4: StackOverflow. Lolwut?

let rec yoba4<'a> = Seq.filter ((<>) [])
                 >> Seq.groupBy List.head
                 >> Seq.sortBy fst
                 >> Seq.map (uncurry (flip (Seq.map List.tail
                                         >> yoba4 // Minimized ">> fun values -> yoba4 values"
                                         >> fun nextNodes -> fun key -> Node (key, nextNodes))))
                 >> Seq.toList

testData |> yoba4 |> printfn "test4: %A"

//-----------------------------------------------------------------------------------

System.Console.ReadKey true |> ignore
.

See section 14.6.6 of the spec (Recursive Safety Analysis), which includes a note which specifically mentions that the current version of F# doesn't perform the analysis for generic bindings.

Your yoba3 is analogous to 

1
2

let rec x = x + 1

, which the compiler flags as an error since it is clearly self-referential.

Your yoba4 is analogous to 

1
2

let rec x<'a> = x + 1

, which the compiler allows, but which causes a stack overflow at runtime if you try to evaluate x<_>.

By on 7/10/2010 6:58 PM ()

Your yoba4 is analogous to 

1
2

let rec x<'a> = x + 1

, which the compiler allows, but which causes a stack overflow at runtime if you try to evaluate x<_>.

Yeah, stumble on non-existent problem is a real path to success F#. One to one: [link:haskell.pastebin.com]

By on 7/17/2010 4:27 AM ()

One to one: [link:haskell.pastebin.com]

So a lazy language behaves differently from a strict one? I am utterly shocked.

By on 7/18/2010 3:34 AM ()

One to one: [link:haskell.pastebin.com]

So a lazy language behaves differently from a strict one? I am utterly shocked.

Oh yeah, tell me about how it binds a stack overflow with laziness in the 4 test.

By on 7/18/2010 10:00 AM ()

You might also read

[link:blogs.msdn.com]

which has some related stuff that is useful.

By on 7/10/2010 4:08 PM ()

This is all expected behavior. See below for a way to write working code.

F# is a 'strict' language, arguments are evaluated before reducing expressions and calling functions. This is true even for 'values of function type'. You could write e.g.

1
2
3
4
5
6
7
8
9
10
11

let rec yoba3a x = 
    x 
    |> Seq.filter ((<>) [])
    |> Seq.groupBy List.head
    |> Seq.sortBy fst
    |> Seq.map (uncurry (flip (Seq.map List.tail
                                >> fun values -> yoba3a values
                                >> fun nextNodes -> fun key -> Node (key, nextNodes))))
    |> Seq.toList
 
testData |> yoba3a |> printfn "test3: %A"

which would be more idiomatic, but styled more like you have it, you can do this: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#nowarn "40"
let flip f a b = f b a
let curry f a b = f (a, b)
let uncurry f (a, b) = f a b
type Tree<'a> = Node of 'a * Tree<'a> list
let testData = [[1; 2; 3]; [1; 2; 4]; [1; 2; 3; 5]]
//-----------------------------------------------------------------------------------
let rec yoba1 = 
    Seq.filter ((<>) [])
    >> Seq.groupBy List.head
    >> Seq.sortBy fst
    >> Seq.map (fun (key, values) -> Node (key, yoba1 (Seq.map List.tail values)))
    >> Seq.toList
 
testData |> yoba1 |> printfn "test1: %A"
//-----------------------------------------------------------------------------------
let rec yoba2 = 
    Seq.filter ((<>) [])
    >> Seq.groupBy List.head
    >> Seq.sortBy fst
    >> Seq.map (uncurry (flip (Seq.map List.tail
                                >> fun values -> yoba2 values
                                >> fun nextNodes -> fun key -> Node (key, nextNodes))))
    >> Seq.toList
 
testData |> yoba2 |> printfn "test2: %A"
//-----------------------------------------------------------------------------------
let rec yoba3() = 
    Seq.filter ((<>) [])
    >> Seq.groupBy List.head
    >> Seq.sortBy fst
    >> Seq.map (uncurry (flip (Seq.map List.tail
                                >> fun values -> yoba3() values
                                >> fun nextNodes -> fun key -> Node (key, nextNodes))))
    >> Seq.toList
 
testData |> yoba3() |> printfn "test3: %A"
 
//-----------------------------------------------------------------------------------
let rec yoba4<'a>() = 
    Seq.filter ((<>) [])
    >> Seq.groupBy List.head
    >> Seq.sortBy fst
    >> Seq.map (uncurry (flip (Seq.map List.tail
                                >> fun values -> yoba4() values
                                >> fun nextNodes -> fun key -> Node (key, nextNodes))))
    >> Seq.toList
 
testData |> yoba4() |> printfn "test4: %A"
//-----------------------------------------------------------------------------------
System.Console.ReadKey true |> ignore
By on 7/10/2010 3:49 PM ()

StackOverflow is the expected behavior? Are you serious?

By on 7/10/2010 4:10 PM ()

I think you effectively wrote

1

let f() = ... f() ...

though I can't seem to untangle this code into a simpler repro that demonstrates it. Note the relationship with GeneralizableValueAttribute in the article I linked.

Note what happens with

1
2
3

printfn "we get here"
yoba4 |> ignore
printfn "but not here"
By on 7/10/2010 5:53 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper