Back to Questions
1.4k
views9
comments
"TransFold" searchic for ideomatic function or name.
f#

I've been searching for a name of a concept that crops up from time to time that is basicly this:

Given a sequence

* do something with the first element
* do something slightly diffrent with the remaining elements.

One usage is to build a comma separated string where something and something else would be

* append item
* append ", item"

Implementationwise one possibility is this:

1
2
3
4
5
6
7
8
9
10
11

let TransFold first acc (items:seq<'a>) =
    use iter = items.GetEnumerator()
    let rec loop acc x =
        if iter.MoveNext() then
            loop acc (acc (x,iter.Current))
        else
            x
    if iter.MoveNext() then
        loop acc (first iter.Current)
    else
        raise (ArgumentException "the input sequence was empty")

And usage would be:

1
2
3
4
5

[1; 2; 3]
|> TransFold
    (fun x -> (new StringBuilder()).Append(x))
    (fun (acc,x) -> acc.AppendFormat(", {0}", x))
|> print_any

yielding "1,2,3"

Is there a name for this operation? A "Core" function that accomplish it? Anything?
Or maybe a better implementation?

.

I quite often use the Seq.mapi for this sort of functionality. It's like a map but you also get the index so its easy to tell if it's the first element or not.

Cheers,

Rob

By on 9/10/2008 1:23 AM ()

Yes that was my thought to but putting an if that will only ever be true for the first element feels a bit odd.

Thanks.

By on 9/10/2008 1:25 AM ()

Agreed, but I prefer it to a function that accepts one function for the first value and another for all the rest.

If the aim is add a separator in-between a list of values, then I'd probably just define a function to do that:

1
2
3

let addSep sep list = 

    ...

I think there's some danger in trying to make functions too general, but I guess a lot of it comes down to taste.

Cheers,

Rob

By on 9/10/2008 2:18 AM ()

The problem is that it has popped up in a number of contexts and I started to feel that there ought to be some sort of generalization of the concept. But it's equally possible that I've just stumbled upon and built things that are flawed in the same way as to need this.

I agree on the issue of over generalization for lists I guess it's semanticly equivalent with pseudo

1
2

List.tl list
|> List.fold_left rest (List.hd list |> first)

Oh maybe Im just seeing a pattern where non exists, or simply it's not usefull enough :)

Thanks for all your input.

By on 9/10/2008 2:36 AM ()

Actually, your right I've seen this crop up in a few other place too. The Seq.reduce (previously Seq.fold1) can be used to do something similar but, it takes the first element and uses it to initialise the accumulator.

1

let res = seq { 1 .. 10 } |> Seq.map (fun x -> x.ToString()) |> Seq.reduce(fun acc x -> acc + Printf.sprintf ", %s" x )
By on 9/10/2008 3:21 AM ()

I encountered the same pattern in my system a couple of times already when I was trying to print a nice output for a list e.g.

Still, writing that simply as

1
2
3
4
5
6
7

let print_list lst = 
    let rec print_lst_h lst =
        match lst with
            | [] -> "]"
            | [last] -> last + "]"
            | hd::tl -> hd + ", " + (print_lst_h tl)
    printfn "[%s" (print_list_h lst)

Note that here I also need a special case for an empty list.

Now there's so many special cases for a generalization:

I need to tell that function:

- What to do if the list is empty

- What to do if there is one element

- If there are two or more elements:

-> What to do with the first element

-> What to do with the last element

-> What to do with all the elements in between

Writing out all those functions probably defeats the purpose of abstracting, since you'll be writing more code in the end (and it would be harder to understand).

Daniel

By on 9/10/2008 4:21 AM ()

I agree that there's many potential "what if" points and as you can see in my inital implementation I've modeled it after the "fold" constraint that an empty sequence is an error.

You could write your PrintList like this by using list op's.

1
2
3
4
5
6

let PrintList lst =
    let items = function
    | [] -> ""
    | hd::tl ->
        List.fold_left (fun x y -> x + "," + y) hd tl
    printf "[%s]" (items lst)

:) Thanks for your input.

By on 9/10/2008 5:47 AM ()

In Haskell there's intersperse:

1

intersperse :: a -> [a] -> [a]

The intersperse function takes an element and a list and `intersperses' that element between the elements of the list. For example, 

1

intersperse ',' "abcde" == "a,b,c,d,e"

Very handy indeed if you're printing lists.

Kurt

By on 9/10/2008 7:58 AM ()

Handy indeed, and a lot like "String.Join"

While mulling over the name I realized that "TransFold" my first name for it actually was quite close what it really is, only that since I got a past in C++ I tend to Transform rather than Map things. When this obvious fact clicked I realized that actually what it is is a Map followed by a Fold, this can easily be deduced by nothing that the first function goes from 'a -> 'b and the following functions need to accumulate, err, fold from 'b - 'a -> 'b.

Still lacking a name for it though, "Mold" is cute but I guess some people would object to naming a concept like that.

Or maybe it's time to let the subject get some rest, probably easy enough to re-solve this problem until an obviously better solution appears.

By on 9/10/2008 2:26 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