Back to Questions
2.1k
views9
comments
Seq/List.reduce with Variable State
f#

I'm playing with the reduce function (Which is great BTW) but I'm having a problem with how its implemented. The nice thing about fold is that your state can be of any type:

val fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State

But the reduce function requires that the state and item type be the same:

val reduce : ('T -> 'T -> 'T) -> 'T list -> 'T

One of the common things I often do is take a list or sequence and reduce it to a string, so for example I'd love to be able to do this:

let values = [1; 5; 22; 45]

Console.WriteLine(List.reduce (fun accumulator item -> accumulator + ", " + item.ToString()) values)

Console.ReadKey() |> ignore

So along the lines of:

val reduce : ('State -> 'T -> 'State) -> 'T list -> 'State

Anyways, is there a reason that reduce differs from fold in that the state must be of the same type as the item? Are there plans to change this? Also, as I'm a real noob with F# and probably missing something, is there another way to do this?

TIA,

m

.

Here it is done with a fold, sorry about the mess

let forbrianmcn ls =
(List.fold (fun (acc: System.Text.StringBuilder) (x: int) ->
if (acc.Length > 0) then ignore (acc.Append(", "))
ignore (acc.Append(x.ToString()))
acc.Append(".00")) (new System.Text.StringBuilder()) ls).ToString()

I just looked at this thread and thought that someone should have pointed out by now that the accumulator passed through a fold should be a StringBuilder. It makes perfect sense that way. It doesn't implement idea of using reduce the way you want it to be used, you would have to implement that on your own. However, since a string accumulator is build into the BCL you may as well use it for its intended purpose

By on 8/31/2009 6:30 AM ()

They have different boundary conditions that constrain the behavior in a fashion that makes a lot of sense under close scrutiny:

reduce f [] // raises an exception
reduce f [x] // returns x
reduce f [more than 1 element] // starts apply f successively

fold f orig [] // returns orig
fold f orig [x] // f orig x
fold f orig [more than one] // (f (f orig x1) x2) ...

The key is that when the return type is different from the list, you must pass a 'seed'/'original' value of that type, else fold has no clue how to construct an object of that type.

(If you want to get wild and abstract, you can talk about the algebraic 'unit's for the operator f (such that f unit x = x, and thus you could return the unit when applied to the empty list), where e.g. if f = (*) then '1.0' could be a unit, and for your string-concatenation, the empty string could be a unit (though not quite in your example), and for addition, zero could be a unit, and then imagining that F# could magically infer the unit of the operation and implicitly pass that as the seed accumulator to fold. That seems like what you wish for, but that would still be 'magic' for the most part. Better to force you to pass 'and here's the result that makes sense for the empty list' for fold.)

By on 8/13/2009 10:37 AM ()

Ok, I see what your saying. I was thinking that it could somehow infer the return type from the accumulator function body. I do agree that would be pretty magical... :)

You know what would be cool though is if it would work if you did this:

let value = List.reduce (fun (accumulator : string) item -> accumulator + ", " + item.ToString()) values

So if you explicitly specified the type of the accumulator if could then infer the type from that.

By on 8/13/2009 11:11 AM ()

I think Brian is saying this isn't an issue of type -- it's an issue of seed value.

Just because reduce "knows" the seed is an integer doesn't mean that it should be 0 (could be some previous sub-total), and just because it's a string doesn't mean it's "" -- could be "My list:", for example.

By on 8/13/2009 11:17 AM ()

It seems though that the first item in the list would be the seed (If I'm understanding reduce correctly...), so we do have a seed value just not in the type and format desired. From what I'm gathering the issue is figuring out the accumulator type. Also that getting the first element converted to the accumulator type and format is an issue. That would be a problem unless another function was required to convert the first element.

So with the reduce function the first call has the first item as the accumulator (Or seed) and the item as the second item. So with the following:

let values = [1; 5; 22; 45]

List.reduce (fun accumulator item -> accumulator + item) values

Would do this:

1) fun 1 5 -> 1 + 5

2) fun 6 22 -> 6 + 22

3) fun 28 45 -> 28 + 45

So in the above example the first element 1 would be the seed. But if we we did this:

let value = List.reduce (fun (accumulator : string) item -> accumulator + ", " + item.ToString(".00")) values

It could figure out that the accumulator was a string but it doesn't know how to convert the first element (The seed) from an int to a string in the format that might be desired (Like in the example above we show two decimal places). If it used some default type converter it would look like this:

"1, 5.00, 22.00, 45.00"

So for this to work we'd have to be able to infer the accumulator type from the accumulator function and have a function to convert the type of the first/all the items.

Anyways, just thinking out loud. :)

m

By on 8/13/2009 11:51 AM ()

So for this to work we'd have to be able to infer the accumulator type from the accumulator function and have a function to convert the type of the first/all the items.

This really sounds like a composition of map and reduce, no need for a new function.

1

value |> Seq.map (fun i -> i.ToString(".00")) |> Seq.reduce (fun acc s -> acc + ", " + s)

/edit

> So in the above example the first element 1 would be the seed.

The seed is 0 [...]

There's certainly no 0 involved in the expression. The expansion is f (f (f 1 5) 22) 45. You'd need a 1/0 seed for fold, not reduce.

By on 8/13/2009 12:50 PM ()

Kha, you are a genius! Thats *exactly* what I was looking for, thanks!

By on 8/13/2009 1:01 PM ()

> So in the above example the first element 1 would be the seed.

The seed is 0, because (a) you're implicitly "starting from scratch (0)", and (b) becuase you're using "+". If you were using "*" then presumably you'd need to use a 1 as your seed, or you'll be spending alot of time computing another 0. Altough the compiler could, I suppose, pick a "ground" seed/terminal for algebraic (+ vs. *, etc.) and simple primitive types (strings), it certainly wouldn't know what to do if your type was a complex class and your reduction operation some piece of code that goes to a database, etc.

If you were computing grand-total from some sub-total, for example, you may use it rather than the first item in your list - if it were always the first item in the list, then you'd have to cons another list just to get things rolling.

By on 8/13/2009 12:40 PM ()

anotheraccount,

I'm not sure I understand what your saying. From what I can see the reduce function uses the first element of the list as the seed. Thats why you don't pass a seed in. When you use fold your "starting from scratch" so you do need a seed but not so with reduce. So if we have:

let values = [50, 100, 150]

List.reduce (fun accumulator item -> accumulator + item) values

Wouldn't 50 be the seed? Basically the *first* call to the accumulator would be:

fun 50 100 -> 50 + 100

The accumulator being the first element and the item being the second element. I'm just digging into this so let me know where I'm going wrong.

Thx,

m

By on 8/13/2009 1:08 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