Back to Questions
2.3k
views1
comment
Remove equal parts at the ends of the two lists.
f#functionalpattern matchinglist

Because lists and pattern matching are the working horses of the functional language F#,
I want to do trimEnds (see below) in a functional style without a performance penalty of List.rev.
It looks very easy, but I need a good idea, it should look like trimStart.

Pattern matching is nice for the head::tail but I found nothing elegant and fast for "leadings::end", any idea?
Btw. these functions are needed for a LCS algorithm (longest common subsequence).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    /// Remove equal parts of the beginning of the two lists xs and ys.
    let rec trimStart xs ys =
        match xs, ys with 
        | x::xt, y::yt when x=y -> trimStart xt yt
        | _ -> xs,ys           

    // TEST
    let xs = [2;4;7;3;2]
    let ys = [2;4;7;1;6;3;2]
    trimStart xs ys = ([3; 2], [1; 6; 3; 2]) // true


    /// Remove equal parts at the ends of the two lists xs and ys.
    // ToDo: it works, but the reversing overhead is too much? Any better functional solution?
    let trimEnds xs ys =
        let rev xs = List.rev xs
        let revTuple (xs,ys) = (rev xs, rev ys)
        trimStart (rev xs) (rev ys) |> revTuple

    // TEST
    let xs = [2;4;7;3;2]
    let ys = [2;4;7;1;6;3;2]
    trimEnds xs ys = ([2; 4; 7], [2; 4; 7; 1; 6])
.

The problem here is that in F# (and most other functional languages), the list type is an immutable linked list. The reason List.rev is slow is because it has to traverse the entire list it's given, then create an entirely new data structure representing the reversed list.

I think the ideal solution would simply use arrays, unless there is a special reason you want to keep the sequence data in lists. Also, IMO, using arrays instead of lists doesn't make the code less "functional" -- you could still write a clean, recursive implementation of LCS based on them.

By on 1/3/2012 6:34 AM ()

    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