Zėŋōfōbìå

11 agosto 2009

C# e paradigma funzionale

Filed under: C#, Haskell, informatica — Tag:, — Zeno @ 11:25

Ho trovato un bell’articolo pratico su come implementare alcune funzioni di ordine superiore che si incontrano sempre nei linguaggi funzionali. In particolare faccio riferimento alle implementazioni di Haskell: Curry, Zip, ZipWith.

Ho aggiunto Map, Filter, FoldR e FoldL e qualche test case.

 public static class Functional
    {
        public static IEnumerable< V > Map< V,T >( 
			this Func< T, V > func, IEnumerable< T > t)
        {
            return from el in t select func(el);
        }

        public static IEnumerable< T > Filter< V, T >
			(this Predicate< T > func, IEnumerable< T > t)
        {
            return from el in t where(func(el)==true) select el;
        }

        public static T FoldL< T >(Func<t , T, T> function,
                                 T seed,
                                 IEnumerable< T > list)
        {

            return list.Aggregate(seed, function);

        }
        public static T FoldR< T >(Func< t , T, T > function,
                                 T seed,
                                 IEnumerable< T > list)
        {
            return list.Reverse().Aggregate(seed, function);

        }


        /// thanks to Xoltar

        //Convert a 1-arg function to a 0-arg thunk by binding an argument
        public static Func< Z > Curry< T, Z >(this Func< T, Z > func, T t)
        {
            return () => func(t);
        }

        //Convert a 2-arg function into a 1-arg function by binding the first argument
        public static Func< U, Z > Curry< T, U, Z >(this Func< T, U, Z > func, T t)
        {
            return (u) => func(t, u);
        }

        public static IEnumerable< V > ZipWith< T, U, V >(Func< T, U, V > f,
           IEnumerable< T > en1, IEnumerable< U > en2)
        {
            //We're working with sets that happen to be implicitly indexed. We need to
            //make that index explicit in order to connect the two enumerables.
            var e1i = en1.Select((x, i) => new { Index = i, Value = x });
            var e2i = en2.Select((x, i) => new { Index = i, Value = x });

            //Sql-like syntax and method-call syntax just two ways to say the same thing
            var zipped = from e1 in e1i
                         join e2 in e2i on e1.Index equals e2.Index
                         select f(e1.Value, e2.Value);
            //Another way to say the exact same thing:
            //var zipped2 = e1i.Join(e2i, 
            //                    lhs => lhs.Index, 
            //                    rhs => rhs.Index, 
            //                    (e1, e2) => f(e1.Value, e2.Value));
            return zipped;
        }

        public static IEnumerable< Pair< T, U > > Zip< T, U >
			(IEnumerable< T > ts, IEnumerable< U > us)
        {
            
            return ZipWith((x, y) => new Pair< t , U > { First = x, Second = y }, ts, us);
        }
    }

Un uso possibile:
Supponiamo di avere un array di caratteri e un array di interi, vogliamo produrre una stringa che abbia l’ennesimo carattere ripetuto un numero di volte specificato nel secondo array. (RLE compression)

Seguono i test case.

    [NUnit.Framework.TestFixture]
    [NUnit.Framework.Category("Utils Tests")]
    public class UtilsTest
    {
        [Test]
        public void FoldLTest1()
        {
            List<int> SampleList = new List</int><int>() { 1, 1, 2, 3, 5, 8, 13 };
            int AggCount = Functional.FoldL((counter, listItem) => counter + listItem,0,SampleList);
            int CalculedCount=0;
            foreach (int i in SampleList)
            {
                CalculedCount += i;
            }
            Assert.That(AggCount == CalculedCount);
        }

        [Test]
        public void FoldRTest1()
        {
            List</int><int> SampleList = new List</int><int>() { 1, 1, 2, 3, 5, 8, 13 };
            int AggCount = Functional.FoldR((counter, listItem) => counter + listItem, 0, SampleList);
            int CalculedCount = 0;
            foreach (int i in SampleList)
            {
                CalculedCount += i;
            }
            Assert.That(AggCount == CalculedCount);
        }

        [Test]
        public void FoldLTest2()
        {
            int numelements = 25;
            Char[] tokens = Enumerable.Range(65, numelements).Select(x => (char)(x % numelements)).ToArray();            
            var words = Functional.Map(x => x.ToString(), tokens);


            string alphabet=Functional.FoldL((first, second) => first + second, "", words);


            string calculedAlphabet = "";
            foreach(var word in words)
            {
                calculedAlphabet += word;
            }

            Assert.AreEqual(calculedAlphabet, alphabet);

        }

        [Test]
        public void FoldRTest2()
        {
            int numelements = 25;
            Char[] tokens = Enumerable.Range(65, numelements).Select(x => (char)(x % numelements)).ToArray();
            var words = Functional.Map(x => x.ToString(), tokens);


            string retroalphabet = Functional.FoldR((first, second) => first + second, "", words);

            string calculedAlphabet = "";
            foreach (var word in words)
            {
                calculedAlphabet = word + calculedAlphabet;
            }

            Assert.AreEqual(calculedAlphabet, retroalphabet);

        }

        [Test] 
        public void ZipWithTest()
        {
            int numelements = 25;
            string expected =
                "ABBCCCDDDDEEEEEFFFFFFGGGGGGGHHHHHHHHIIIIIIIIIJJJJJJJJJJKKKKKKKKKKKLLLLLLLLLLLLMMMMMMMMMMMMMNNNNNNNNNNNNNNOOOOOOOOOOOOOOOPPPPPPPPPPPPPPPPQQQQQQQQQQQQQQQQQRRRRRRRRRRRRRRRRRRSSSSSSSSSSSSSSSSSSSTTTTTTTTTTTTTTTTTTTTUUUUUUUUUUUUUUUUUUUUUVVVVVVVVVVVVVVVVVVVVVVWWWWWWWWWWWWWWWWWWWWWWWXXXXXXXXXXXXXXXXXXXXXXXX";

            Char[] tokens = Enumerable.Range(65, numelements).Select(x => (char)x).ToArray();
            int[] times = Functional.Map(x=> x%numelements,Enumerable.Range(1, numelements)).ToArray();
            Assert.That(tokens[0] == 'A');
            Assert.That(times[0] == 1);
            Assert.That(tokens.Length == times.Length);
                        
            var zip=Functional.ZipWith((x, y) => "".PadLeft(y,x), tokens, times);

            string rle = Functional.FoldL((x,y) => x + y, "", zip);

            Assert.That(expected == rle);
        }
    }

Annunci

5 commenti »

  1. Direi tutto molto bello! Gli Extension Method per queste cose sono davvero comodi! :D

    Gran bel post! :)

    Ho provato a rendere variadic la funzione/metodo Curry() ma nada… Non so se la mia idea è bacata, c’è qualche regola che vieta Extension Method con parametri variadici o che altro.. In ogni caso si può simulare la cosa passando un oggetto-lista. :)

    Ciau! ^^

    Commento di jp — 11 agosto 2009 @ 12:27

  2. mi piace molto la sintassi SQL-like che si vede qui e là. si chiama LINQ ?

    Commento di g2-67f1108eabf701ed53b05a875e3d8203 — 12 agosto 2009 @ 11:09

    • Sì. (1)

      Zucchero sintattico, se vuoi.
      Infatti sono operatori di query che vengono convertiti in chiamate a metodi “extension”. (2)
      I metodi extension a loro volta sono zucchero sintattico: sono metodi statici che si aggiungono a caldo a delle classi, anche sealed.
      Per esempio, se vuoi aggiungere alla classe DateTime il metodo IsWeekend:

      public static bool IsWeekend(this DateTime value)
      {
          return (value.DayOfWeek == DayOfWeek.Sunday || value.DayOfWeek == DayOfWeek.Saturday);
      }
      

      A quel punto puoi fare:

      bool NowIsWeekend=DateTime.Now.IsWeekend();
      

      In pratica con questo trucco è stato aggiunto il metodo select ai tipi generici che implementano l’interfaccia IEnumerable .
      quindi se hai una lista list, puoi scrivire list.select(...)

      Linq permette di trasformare “from l in list select ...” nella sua forma convenzionale.

      (1) http://en.wikipedia.org/wiki/Language_Integrated_Query
      (2) http://extensionmethod.net/

      Commento di Fabrizio — 12 agosto 2009 @ 13:25

  3. Se hai qualche zilione di neuroni da buttare, dai un’occhiata al blog di Bart De Smet. Warning: è un delirio pazzesco ma mostra la reale potenza in chiave funzionale del futuro C# 4.0…

    Commento di jp — 3 settembre 2009 @ 9:59

  4. @JP: notevole, davvero! L’ho aggiunto ai miei RSS quotidiani. :-)

    Commento di Fabrizio — 10 settembre 2009 @ 8:35


RSS feed for comments on this post. TrackBack URI

Rispondi

Effettua il login con uno di questi metodi per inviare il tuo commento:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Blog su WordPress.com.

%d blogger hanno fatto clic su Mi Piace per questo: