1.1k
views5
comments

I want to go thru an input list and put an output into an output list whenever a criterion is matched. In the two functions below, the only difference is that a match statement is replaced with if-then.

picker1 with the match statement does not do what I want. picker2 with the if-then statement does what I want. Indeed the compiler warns me that the "cleanup" condition in the inner match in picker1 will never be matched. But I don't see why picker1 is not equivalent to picker2.

#light

let input_list = [1;2;3;3;5]

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

let picker1 criterion input_list =
let accumulator = []

let rec picker1_rec crit recur_list accumulator =
match recur_list with
| [] -> accumulator
| h::t -> match h with
| crit -> picker1_rec crit t (1::accumulator)
| _ -> picker1_rec crit t accumulator // WHY does the compiler say that this condition is never matched?

picker1_rec criterion input_list accumulator

let picker1_result = picker1 3 input_list
printfn("picker1 output list = %a") output_any picker1_result

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

let picker2 criterion input_list =
let accumulator = []

let rec picker2_rec crit recur_list accumulator =
match recur_list with
| [] -> accumulator
| h::t -> if (h = crit) then picker2_rec crit t (1::accumulator)
else picker2_rec crit t accumulator // this works as expected

picker2_rec criterion input_list accumulator

let picker2_result = picker2 3 input_list
printfn("picker2 output list = %a") output_any picker2_result

HERE IS THE OUTPUT

val input_list : int list
val picker1 : 'a -> 'a list -> int list
val picker1_result : int list
val picker2 : 'a -> 'a list -> int list
val picker2_result : int list

picker1 output list = [1; 1; 1; 1; 1]
picker2 output list = [1; 1]
>

Why not use List.filter for this?

let picker3 c = List.filter (fun item -> c = item)

let picker3_result = input_list |> picker3 3

printfn "picker3 output list = %A" picker3_result

Or, better, just filter the list directly, as in:

1
2

printfn "picker4 output list = %A" (input_list |> List.filter (fun item -> item = 3) )

(p.s. Anyone know how to indent code lines when posting?)

By jhugard on 3/23/2009 9:35 PM (permalink)

Why not use List.filter for this?
1
2
3
4
5
6
let picker3 c = List.filter (fun item -> c = item)

let picker3_result = input_list |> picker3 3

printfn "picker3 output list = %A" picker3_result
Or, better, just filter the list directly, as in:
1
2
printfn "picker4 output list = %A" (input_list |> List.filter (fun item -> item = 3) )
(p.s. Anyone know how to indent code lines when posting?)

I think the problem with List.filter is that he doesn't necessarily want to write the same element into the output sequence as was in the input sequence. Like suppose you have this function:

let transform_if input cond f =

Which takes an input list and a predicate, and if the predicate is true writes (f x) into the output sequence, and if the predicate is false writes nothing into the output sequence. You could do this by doing List.filter followed by List.map, but this is going to be slow because you have to walk the list twice instead of just once. You could, however, use List.fold_right with your accumulator state value being a list and inside the accumulation function either do nothing with the list, or append (f x) to the front of it.

For indenting code, just put it in a code block and then use spaces to indent. e.g.

let transform_if input pred f = 
    let accum x state = 
        if (pred x) then (f x)::state
        else state

    List.fold_right accum [] input

By divisortheory on 3/24/2009 7:18 AM (permalink)

Which takes an input list and a predicate, and if the predicate is true writes (f x) into the output sequence, and if the predicate is false writes nothing into the output sequence. You could do this by doing List.filter followed by List.map, but this is going to be slow because you have to walk the list twice instead of just once.

List.choose combines List.filter and List.map in one step, as in:

let picker5_result =
    input_list
    |> List.choose (fun item ->
        if item >= 3
        then Some(item+1)
        else None)
printfn "picker5 output list = %A" picker5_result

By jhugard on 3/24/2009 9:45 AM (permalink)

This is a common mistake. What it boils down to is that specifying an identifier on the left hand side of a match condition BINDS that symbol to the matched value. It does not perform a comparison. What I imagine you thought was going to happen is that in picker1, the first match condition would be executed if the head of the list was equal to the first argument of "rec picker1", since the symbol you specified on the LHS of the match and the first argument of the function share the same name. Instead, what will happen is that it will match anything, and that symbol will shadow the previous definition of the symbol. So, once inside the match, "crit" now contains whatever is on the head of the list, the first argument to the function is inaccessible. What you need to do is this:

match recur_list with
            | [] -> accumulator
            | h::t ->   match h with
                            | x when (x=crit) -> picker1_rec crit t (1::accumulator)
                           

| _ -> picker1_rec crit t accumulator

On the other hand, the value is actually already bound to h, so the if/then probably makes more sense.

That being said, is there a reason you can't use List.filter? You say you just want to put something into the output whenever the criterion is matched, sounds like this is a perfect case for List.filter. If you want to transform the input into something else and put that result into the list only when some criterion is met, then you could use List.fold_right() instead. I don't have a compiler handy, but it would be something like this:

1
2

let transform input_list output_val criterion = 
    List.fold_right (fun x,state -> if (criterion x) then (output_val::state) else state) [] input_list

By divisortheory on 3/23/2009 1:24 PM (permalink)

The left of a pattern match, the pattern, is an identifier to bind to. When do you do:

match h with | crit -> picker1_rec crit t (1::accumulator)

You're saying "bind crit to h". This will catch all cases, since all cases can be bound to the identifier "crit". The fact you have an existing identifier named "crit" is irrelevant; you're shadowing it with this pattern.

Edit: oops, I messed up the example :P. Edit2: This is even more clear:
<BR style="mso-special-character: line-break">You need to have a when clause:

match h with | h when crit = h -> ...

In this code, we're re-binding a new "h" (to the same value of the match "h"), only when h equals crit.

By Michael Giagnocavo on 3/23/2009 1:19 PM (permalink)

Topic tags

Built with WebSharper

Home

Answers

Events

Courses

Groups and Conferences

Blogs

Jobs

Developers

Topic tags