Return value in F# - incomplete construct

Question

I've trying to learn F#. I'm a complete beginner, so this might be a walkover for you guys :)

I have the following function:

let removeEven l = 
 let n = List.length l;
 let list_ = [];
 let seq_ = seq { for x in 1..n do if x % 2 <> 0 then yield List.nth l (x-1)}
 for x in seq_ do
  let list_ = list_ @ [x];
 list_;

It takes a list, and return a new list containing all the numbers, which is placed at an odd index in the original list, so removeEven [x1;x2;x3] = [x1;x3]

However, I get my already favourite error-message: Incomplete construct at or before this point in expression...

If I add a print to the end of the line, instead of list_:

...
print_any list_;

the problem is fixed. But I do not want to print the list, I want to return it!

What causes this? Why can't I return my list?

Answer 1

Edit: If I understand your requirements correctly, here's a version of your function done functional rather than imperative style, that removes elements with odd indexes.

let removeEven list =
    list
    |> Seq.mapi (fun i x -> (i, x))
    |> Seq.filter (fun (i, x) -> i % 2 = 0)
    |> Seq.map snd
    |> List.ofSeq

> removeEven ['a'; 'b'; 'c'; 'd'];;
val it : char list = ['a'; 'c']

Answer 2

I think this is what you are looking for.

let removeEven list = 
    let maxIndex = (List.length list) - 1;
    seq { for i in 0..2..maxIndex -> list.[i] }
    |> Seq.toList

Tests

val removeEven : 'a list -> 'a list

> removeEven [1;2;3;4;5;6];;
val it : int list = [1; 3; 5]
> removeEven [1;2;3;4;5];;
val it : int list = [1; 3; 5]
> removeEven [1;2;3;4];;
val it : int list = [1; 3]
> removeEven [1;2;3];;
val it : int list = [1; 3]
> removeEven [1;2];;
val it : int list = [1]
> removeEven [1];;
val it : int list = [1]

Answer 3

To answer your question first, the compiler complains because there is a problem inside the for loop. In F#, let serves to declare values (that are immutable and cannot be changed later in the program). It isn't a statement as in C# - let can be only used as part of another expression. For example:

let n = 10
n + n

Actually means that you want the n symbol to refer to the value 10 in the expression n + n. The problem with your code is that you're using let without any expression (probably because you want to use mutable variables):

for x in seq_ do 
  let list_ = list_ @ [x]  // This isn't assignment! 
list_

The problematic line is an incomplete expression - using let in this way isn't allowed, because it doesn't contain any expression (the list_ value will not be accessed from any code). You can use mutable variable to correct your code:

let mutable list_ = [] // declared as 'mutable'
let seq_ = seq { for x in 1..n do if x % 2 <> 0 then yield List.nth l (x-1)}    
for x in seq_ do    
  list_ <- list_ @ [x] // assignment using '<-'

Now, this should work, but it isn't really functional, because you're using imperative mutation. Moreover, appending elements using @ is really inefficient thing to do in functional languages. So, if you want to make your code functional, you'll probably need to use different approach. Both of the other answers show a great approach, although I prefer the example by Joel, because indexing into a list (in the solution by Chaos) also isn't very functional (there is no pointer arithmetic, so it will be also slower).

Probably the most classical functional solution would be to use the List.fold function, which aggregates all elements of the list into a single result, walking from the left to the right:

[1;2;3;4;5] 
  |> List.fold (fun (flag, res) el -> 
     if flag then (not flag, el::res) else (not flag, res)) (true, [])
  |> snd |> List.rev

Here, the state used during the aggregation is a Boolean flag specifying whether to include the next element (during each step, we flip the flag by returning not flag). The second element is the list aggregated so far (we add element by el::res only when the flag is set. After fold returns, we use snd to get the second element of the tuple (the aggregated list) and reverse it using List.rev, because it was collected in the reversed order (this is more efficient than appending to the end using res@[el]).

Answer 4

You can try a pattern-matching approach. I haven't used F# in a while and I can't test things right now, but it would be something like this:

let rec curse sofar ls =
    match ls with
    | even :: odd :: tl -> curse (even :: sofar) tl
    | even :: [] -> curse (even :: sofar) []
    | [] -> List.rev sofar

curse [] [ 1; 2; 3; 4; 5 ]

This recursively picks off the even elements. I think. I would probably use Joel Mueller's approach though. I don't remember if there is an index-based filter function, but that would probably be the ideal to use, or to make if it doesn't exist in the libraries.

But in general lists aren't really meant as index-type things. That's what arrays are for. If you consider what kind of algorithm would require a list having its even elements removed, maybe it's possible that in the steps prior to this requirement, the elements can be paired up in tuples, like this:

[ (1,2); (3,4) ]

That would make it trivial to get the even-"indexed" elements out:

thelist |> List.map fst // take first element from each tuple

There's a variety of options if the input list isn't guaranteed to have an even number of elements.

Answer 5

Yet another alternative, which (by my reckoning) is slightly slower than Joel's, but it's shorter :)

let removeEven list =
    list
    |> Seq.mapi (fun i x -> (i, x))
    |> Seq.choose (fun (i,x) -> if i % 2 = 0 then Some(x) else None)
    |> List.ofSeq