Back to Questions
1.2k
views6
comments
How would I do this the F# way? Sequence Composition?
f#

I have thought about this problem for a bit, looked at examples, and googled, but I haven't found anything that seems close to what I am asking. Although I believe that F# is well suited to handle this problem, and someone here probably can give some help.

I have a seq like:

1

let seq0 : seq<char> = seq ['a'; '1'; 'b'; '2'; '3'; 'c'; '4'; '5'; '6']

I want a seq of seqs like this:

1

lets seq1: seq<seq<char>> = seq [ seq ['a';'1']; seq ['b';'2';'3']; seq ['c';'4';'5';'6']];;

Basically, my test is if the char is a letter instead of a number. Of course my real world example is not this simple, but this makes it easier to distill the problem. I would welcome any suggestions on how I should attack this. I have started and stopped several times and am at a loss... :(

Thanks,

Scott

.

fold/scan are what you are looking for:

1
2
3
4
5
6
7
8

let numbers =
    [0..9]
    |> Seq.map (string >> char)
    |> Set.ofSeq
['a'; '1'; 'b'; '2'; '3'; 'c'; '4'; '5'; '6']
|> List.rev
|> List.fold (fun (current, processed : char list list) v -> if numbers.Contains v then (v :: current, processed) else ([], (v :: current) :: processed)) ([], [])
|> snd

scan returns every intermediate state so there might be a way to do it with scan too but the only one I could find had my solution as the very last element so I reverted to fold.

I really recommend reading everything on fold/unfold in Real World Haskell. It was a very heavy thought process but these things are powerful. I think the book is available for free only as creative commons.

David

By on 6/21/2011 8:10 PM ()

Thanks David- especially about the recommendation for a resource on how to 'learn to fish'... ;)

Thanks,

Scott

By on 6/21/2011 8:17 PM ()

David- I wanted to expose this to c# so I went with Seq rather than list. Perhaps I am incurring a performance hit. But I refactored the code to match this change. However, I do not recieve the same answer as you. Am I required to use lists to solve this problem? Btw I know I could probaby cast your solution back to Seqs, but why do that if I can avoid them all together?

1
2
3
4
5
6
7
8

let collectChars(chars : seq<char>) =
   chars
   |> Seq.fold(
      fun (curr, proc : seq<seq<char>>) v ->
         if Char.IsLetter(v)
         then (Seq.singleton(v) |> Seq.append(curr), proc)
         else (Seq.empty, Seq.singleton(Seq.singleton(v) |> Seq.append(curr)) |> Seq.append(proc))) (Seq.empty, Seq.empty)
   |> snd

I receive the following:

1
2

val it : seq<seq<char>> =
seq [seq ['a'; '1']; seq ['b'; '2']; seq ['3']; seq ['c'; '4']; ...]
By on 6/21/2011 9:24 PM ()

I agree you can stick with sequence, but you introduced two bugs while doing it.

1- In the example I provided, I fold over the reverse of the list. I couldn't find the rev function in the Seq module that's why I stuck with List. You can import System.Linq and use Enumerable.Reverse.

2- Seq.append seems to append the element at the end, while with the list (::) operator I'm adding the element at the beginning, I think you'll have to do that if you process the collection backward like I do.

Note that C# 3 brought a lot of excellent options to the functional table and you can do this with Linq using the Aggregate extension method as well.

By on 6/22/2011 4:21 AM ()

I don't know if this is any better, but I sure did learn a lot getting here... ;)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

let collectChars(chars : seq<char>) =

        let pair = chars |> Seq.fold(  fun (curr, proc:seq<seq<char>>) c ->

                           if Char.IsLetter(c)

                            then (Seq.singleton(c), Seq.singleton(curr) |> Seq.append(proc) )

                            else (Seq.singleton(c) |> Seq.append(curr), proc)

                            ) (Seq.empty, Seq.empty)

        Seq.singleton(fst(pair)) |> Seq.append(snd(pair))

        |> Seq.skip(1)
By on 6/22/2011 2:11 PM ()

And yes I am aware of the Aggregate method in Linq in C#. I found some implementations of Folds and added them to my extension libraries. It helped me debug and figure out what was really going on. I even wrote a version of the above code in C# first! ;) I wasn't abel to get an equivalent of the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var result = chars.Fold<List<List<char>>, char>((acc, c) =>
			    {
			        if (Char.IsLetter(c))
			        {
			            var listOfChars = new List<char> { c };
			            acc.Add(listOfChars);
			        }
			        else
			        {
			            var listOfChars = acc.Last();
			            listOfChars.Add(c);
			        }
			        return acc;
			    }, new List<List<char>>());

Here are the support functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static TAcc Fold<TAcc, TItem>(this IEnumerable<TItem> items, Func<TAcc, TItem, TAcc> func, TAcc acc)
		{
			foreach (var item in items)
				acc = func(acc, item);
			return acc;
		}
		public static TAcc FoldLeft<TAcc, TItem>(this IList<TItem> items, Func<TAcc, TItem, TAcc> func, TAcc acc)
		{
			for (int index = 0; index < items.Count; ++index)
				acc = func(acc, items[index]);
			return acc;
		}
		public static TAcc FoldRight<TAcc, TItem>(this IList<TItem> items, Func<TAcc, TItem, TAcc> func, TAcc acc)
		{
			for (int index = items.Count - 1; index >= 0; ++index)
				acc = func(acc, items[index]);
			return acc;
		}
By on 6/22/2011 2:17 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