CODEWITHSUNDEEP
listtypesfunctional-programmingf#
Maurdekye
Maurdekye

Reputation: 3677

Generic types on function don't correspond properly

I have experience with functional programming in general, but I'm new to F#, and I can't get this code to compile no matter what I try:

let group2<'T> (sq: seq<'T>) : seq<'T * 'T> = 
    Seq.fold (fun (p, l) b -> match p with
                              | None   -> (Some b, l)
                              | Some v -> (None, (v, b) :: l)) (None, []) sq

I don't understand what this error message is trying to tell me, and I can't for the life of me figure out why it won't compile as-is;

main.fs(2,19): error FS0001: This expression was expected to have type
    'seq<'T * 'T>'    
but here has type
    ''a * 'b'    

main.fs(4,65): error FS0001: This expression was expected to have type
    'seq<'T * 'T>'    
but here has type
    ''a * 'b'

anyone with more F# experience have some advice?

Upvotes: 0

Views: 79

Answers (1)

Koenig Lear
Koenig Lear

Reputation: 2436

So if you update your code like this

let group2<'T> (sq: seq<'T>) : seq<'T * 'T>  = 
    Seq.fold (fun (p ,l) b -> match p with
                              | None   -> (Some b, l)
                              | Some v -> (None, (v, b) :: l)) (None, []) sq
    |> snd
    |> List.rev
    |> Seq.ofList

It can work (by removing the state, and converting back from list to sequence). For example

group2 [1;2;3;4]

yields

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

It's not very idiomatic as it mixes sequences and lists.

A more idiomatic code only for (even) lists:

let rec group2 (xs:'T list) =
    match xs with
    | [] -> []
    | x::y::xs -> ( x, y)::group2 xs
    | _ -> failwith "not even"

Basically you deal with 3 choices,

  1. The list is empty, there are no pairs you return an empty list.
  2. There are two items at the start, you pair them in a tuple and process the rest of the list recursively
  3. There's only one item left, we fail because it's not posible to create a tuple with nothing*

If you want to consider odd lists, you can use option types: e.g. None/Some

let rec group2 (xs:'T list) =
    match xs with
    | [] -> []
    | [x] -> [Some x, None]
    | x::y::xs -> (Some x,Some y)::group2 xs

Finally you could use the chunkBySize library function for either (even) lists or sequences:

[1;2;3;4]
|> Seq.chunkBySize 2
|> Seq.map (fun a -> a.[0], a.[1])

or

[1;2;3;4]
|> List.chunkBySize 2
|> List.map (fun a -> a.[0], a.[1])

Upvotes: 2

Related Questions