LINQ Recipe No. 2-13: How to Generate Fibonacci Numbers Nonrecursively

Contents

1. Introduction
2. Keywords
3. Problem
4. Solution
5. Discussion
5.1 Fibonacci numbers
5.2 Nonrecursive way to compute Fibonacci numbers
6. Practice: Fibonacci Numbers Generation
7. Conclusions
8. Literature & Links

1. Introduction

Functional programming with LINQ is amazing! In this new LINQ recipe we will be to able to compute Fibonacci numbers in a non-recursive fashion. For this, as we will see soon, we just only need to sum up the last previous numbers.

2. Keywords

• Fibonacci
• Functional programming
• Recursivity

3. Problem

Generate Fibonacci numbers using a nonrecursive algorithm.

4. Solution

LINQ allows us to implement an alternative way to compute Fibonacci numbers just using a generator function, and then apply a simple lambda expression over these numbers with the ForEach method from List<T> generic collection.

5. Discussion

5.1 Fibonacci numbers

The Fibonacci serie is sequence of integer positive values. These numbers are defined by the recursive relation ("Fibonacci number", 2016): 

and these are the base cases or seed values: 

For example: 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

There are a lot of interesting mathematical facts which are based on this recursive relation; for example: 

• Divisibility properties, 
• Fibonacci primes, 
• Periodicity modulo n, 
• Primality testing

But this series is also expressed in nature: the length of the algae string is at each growth stage is equal to Fibonacci numbers.

But...

5.2 Nonrecursive way to compute Fibonacci numbers

With LINQ we can implement this series using a much faster algorithm: we just need to compute the sum of the last two numbers: this can be accomplished just only using a list data structure to recover the last computed two numbers in the series.

6. Practice: Fibonacci Numbers Generation

In the first place, we must remember that recursion implementations are stateless; this means, in other words, that recursive algorithms are forgetful (Mukherjee, 2014). With this in mind, we need to use a data structure to maintain the computed Fibonacci numbers.

Under that requirement, this is the implementation in LINQ: 

LINQ file NonRecursiveFibonacci.linq [Alternative link][Alternative link]: 

In line 2 we declare and create a List with the parametric type ulong. This will serve us as the data structure to store the computed Fibonacci numbers.

Then, the code defined in lines 6-10 performs these operations: 

• Line 6: Creates a range of integer values from 0 to 200.
• Line 7: Converts the range into a List.
• Lines 8-10: This code computes the Fibonacci numbers following these simple rules: 
• If the given number k is less or equal to 1, the number 1 is added to the list.
• On the contrary, if the previous condition is not met, then the sum of last two numbers in the list are computed.

Finally, the first 53 Fibonacci numbers are shown in the output (line 13).

In this video tutorial an explanation is given to this process: 

7. Conclusions

We have explored a new way to generate Fibonacci numbers: this alternative implementation avoids, eventually, an overflow, and takes less time.

LINQ recipe no. 2-14 will teach us how to generate permutations.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Fibonacci number (2016, July 4). Retrieved from: https://en.wikipedia.org/wiki/Fibonacci_number

V

Receta Multithreading en C# No. 5-2: Operador await en una Expresión Lambda

Índice

1. Introducción
2. Palabras Clave
3. Problema
4. Solución
5. Discusión de la solución
5.1 Operador asincrónico await
5.2 Operador asincrónico async
6. Práctica: Expresión Lambda con Operador Asincrónico await
7. Conclusiones
8. Literatura & Enlaces

1. Introducción

El programador C# puede usar el operador asincrónico await en una expresión lambda. Esta receta multithreading explica cómo usar este operador asincrónico en el cuerpo de declaración, junto con el uso de async en listado de parámetros de la expresión lambda. Para llevar a cabo la demostración programática de esta receta se usará el delegado estándar Func<T, TResult>.

2. Palabras Clave

• Asincronismo
• Expresión lambda
• Sincronismo

3. Problema

Definir la implementación de una expresión lambda usando el operador await.

4. Solución

El cuerpo de la implementación de una expresión lambda puede incluir la invocación de operaciones por medio de await; sin embargo para esto es necesario marcar la firma de la expresión con el operador asincrónico async. Esta expresión lambda quedará declarada sobre un delegado del tipo Func<T, TResult>.

5. Discusión de la Solución

5.1 Operador asincrónico await

(Nota: En la sección 5.1 de Receta Multithreading en C# No. 5-2: Operador await en una Expresión Lambda se detalla el funcionamiento de este operador.)

5.2 Operador asincrónico async

A través del operador asincrónico el programador C# puede marcar un método, expresión lambda o método anónimo como asincrónico ("async (C# Reference)", 2016). Este un ejemplo para marcar un método nombrado: 

public async Task OperacionAsync()
{
// ...
}

Y para el caso de una expresión lambda: 

async param => {
// ...
}

5.3 Delegado Func<T, TResult>

(Nota: En la sección 2.1 de Delegados en C#: Delegados Func y Action de .NET Framework se explica detallamente el funcionamiento de este tipo de delegado.)

6. Práctica: Composición de una Expresión Lambda con el Operador Asincrónico await

La aplicación consola que se ha construido demuestra cómo definir una expresión lambda especificando en su cuerpo de implementación el operador asincrónico await.

Archivo C# AwaitExpresionLambda.cs [Enlace alternativo][Enlace alternativo]: 

El método ProcesamientoAsincronico() (líneas 26-42) se implementa de la siguiente manera: 

• Líneas 31-39: Declaración de delegado por medio de la firma Func<T> con la siguiente expresión lambda:
• Línea 29: Especificación el parámetro nombre antecedido por el operador asincrónico async.
• Línea 31: Invocación asincrónica de tarea que simula ejecución extendida a través del operador await.
• Línea 32-36: Retorno con la información del thread en ejecución en la operación asincrónica.
• Línea 39: Invocación de la expresión lambda por medio del operador asincrónico await.
• Línea 41: Visualización del resultado de la expresión lambda.

Demostración de la ejecución a través de una aplicación basada en consola construida en Visual Studio 2015: 

> Prueba de ejecución (online): http://ideone.com/Mg0XL1

En este enlace de GitHub puede encontrar la solución de Visual Studio 2015 y los proyectos asociados a esta receta y otras más: https://github.com/Fhernd/RecetasMultithreadingCSharp

7. Conclusiones

Se ha demostrado que dentro del cuerpo de una expresión lambda es posible usar la función asincrónica await para invocar otras operaciones asincrónicas. Lo anterior siempre y cuando el programador especifique la función asincrónica async en la firma de parámetros de la expresión.

La siguiente receta multithreading explica cómo usar el operador asincrónico await para llamadas asincrónicas consecutivas de tareas.

8. Literatura & Enlaces

Agafonov, E. (2013). Multithreading in C# 5.0 Cookbook. United States: Packt Publishing.
Receta Multithreading en C# No. 5-1: Obtención de Resultados de Tareas Asincrónicas con el Operador await (2016, junio 26). Recuperado desde: http://ortizol.blogspot.com/2016/06/receta-multithreading-en-csharp-no-5-1-obtencion-de-resultados-de-tareas-asincronicas-con-el-operador-await.html
async (C# Reference) (2016, junio 26). Recuperado desde: https://msdn.microsoft.com/en-us/library/hh156513.aspx?f=255&MSPPError=-2147217396
Delegados en C#: Delegados Func y Action de .NET Framework (2016, junio 26). Recuperado desde: http://ortizol.blogspot.com.co/2014/05/delegados-en-csharp--parte-5-delegados-func-y-action-de-dotnet-framework.html

V

Receta T-SQL No. 4-6: ¿Cómo Hacer una Selección a Partir de un Conjunto de Resultados?

Índice

1. Introducción
2. Palabras Clave
3. Problema
4. Solución
5. Discusión de la Solución
5.1 Subconsulta
6. Práctica: Selección de un Conjunto de Resultados
7. Conclusiones
8. Literatura & Enlaces

1. Introducción

En esta receta T-SQL se enseña cómo hacer una selección sobre un conjunto de resultados devuelto por una cláusula SELECT. Esto se logra a través del uso de cláusulas SELECT anidadas o subconsultas.

2. Palabras Clave

• SELECT
• Subconsulta
• Tabla derivada

3. Problema

Realizar una selección sobre los resultados devueltos por una selección anidada.

4. Solución

En T-SQL se puede realizar una consulta anidada por medio del uso de una cláusula SELECT que retorna una tabla derivada sobre la que se puede realizar cualquier operación común del lenguaje SQL.

5. Discusión de la Solución

5.1 Subconsulta

Una subconsulta es una sentencia T-SQL que se anida o forma parte de otras sentencias como SELECT, INSERT, UPDATE o DELETE. En el caso de la sentencia SELECT una subconsulta seguiría, en principio, esta sintaxis:

SELECT [listado_campo|S.nombreCampo, ...]

    (SELECT [listado_campos] FROM tabla) AS S

    [WHERE condicion];

Una subconsulta siempre va encerrada entre paréntesis, y dentro de ella también podría declararse otras subconsultas; esto último según la complejidad de la consulta.

6. Práctica: Selección en un Conjunto de Resultados

En el siguiente ejemplo (adaptado de Brimhall (2016)) se obtiene los detalles de orden de venta -Sales.SalesOrderDetail- donde el precio unitario ronde entre 1000 y 2000. Esto formará parte de una subconsulta que se nombrará como d. Luego se hace un INNER JOIN entre esos resultados (subconsulta) y la tabla SalesOrderHeader.

SELECT DISTINCT s.PurchaseOrderNumber AS 'No. Orden Compra'

FROM Sales.SalesOrderHeader s

INNER JOIN (SELECT SalesOrderID

FROM Sales.SalesOrderDetail

WHERE UnitPrice BETWEEN 1000 AND 2000

) d

ON s.SalesOrderID = d.SalesOrderID;

La subconsulta empieza a partir de la apertura de y cierre de paréntesis al interior de la consulta general.

Estos son los resultados (reducidos) de la ejecución de la consulta:

Figura 1. Subconsulta con INNER JOIN.

7. Conclusiones

Se enseñó cómo crear una tabla derivada a través del uso de una consulta anidada o subconsulta. Se entendió además que el nivel de anidamiento o número de subconsultas depende la complejidad de la consulta. Además, que una subconsulta siempre está encerrada entre paréntesis.

La próxima receta T-SQL enseña cómo comprobar la existencia de un registro.

8. Literatura & Enlaces

Brimhall, J., Dye, D., Gennick, J., Roberts, A., Sheffield, W. (2012). SQL Server 2012 T-SQL Recipes - A Problem-Solution Approach. United States: Apress.
Subquery Fundamentals (2016, junio 6). Recuperado desde: https://technet.microsoft.com/en-us/library/ms189575%28v=sql.105%29.aspx?f=255

V

Receta T-SQL No. 4-1: ¿Cómo Correlacionar dos Tablas?

Índice

1. Introducción
2. Palabras Clave
3. Problema
4. Solución
5. Discusión de la Solución
5.1 INNER JOIN
6. Práctica: Correlación de las Tablas Person y PersonPhone
7. Conclusiones
8. Literatura & Enlaces

1. Introducción

Con esta receta T-SQL se inicia la serie de recetas enfocadas a la creación de consultas sobre múltiples tablas. Una base de datos está constituida por varias tablas que relacionan los tipos de datos para un dominio de problema; cada tabla mantienen en óptimo estado el almacenamiento de los datos; además de su consistencia e integridad. T-SQL ofrece un conjunto de operadores para especificar las consultas sobre múltiples tablas: la información obtenida permite responder a requerimientos de negocio: los empleados y su sueldo, los pedidos de un cliente, los vuelos realizados por un pasajero, etc. Entre esos operadores se cuentan aquellos que permiten ejecutar operaciones como: joins, uniones, y subconsultas.

En esta primera receta T-SQL se muestra cómo correlacionar datos de distintas tablas. Para esto es necesario el uso del operador INNER JOIN, el cual, como se muestra en la sección práctica, permite la correlación de los datos de dos tablas: Person y PersonPhone.

2. Palabras Clave

• Consistencia
• Correlación
• INNER JOIN
• Integridad
• Producto cartesiano
• Subconsulta
• Tabla

3. Problema

Obtener las personas que tienen por lo menos un número telefónico asociado. Además, indicar por persona los números de cada línea telefónica.

4. Solución

En T-SQL se cuenta con el operador INNER JOIN para correlacionar los registros de dos tablas.

5. Discusión de la Solución

5.1 INNER JOIN

El operador INNER JOIN permite correlacionar dos tablas bajo una condición de correlación -normalmente una llave primaria o un campo con valores en común-. El resultado de la es una tabla que contiene los registros correlacionados del producto cartesiano de las tablas.

Esta es la sintaxis (versión simplificada) para este operador:

SELECT {Proyección de Columnas} 

    FROM {TABLA_1} INNER JOIN {TABLA_2} 

        ON {TABLA_1}.Columna = {TABLA_2}.Columna

    WHERE {Condiciones}

Nótese que frente a la cláusula ON se especifican las columnas bajo las que se correclacionan las tablas a través del operador relacional =.

6. Práctica: Correlación de las Tablas Person y PersonPhone

Este ejemplo (adaptado de Brimhall (2012)) correlaciona dos tablas: 

• Person y 
• PersonPhone

de la base de datos AdventureWorks. Se obtendrá el conjunto de personas que tienen por lo menos una línea teléfono junto con los números asociados a cada una de ellas.

SELECT H.BusinessEntityID AS 'Identificación',

FirstName AS 'Primer Nombre',

LastName AS 'Apellido',

PhoneNumber AS 'Número Telefónico'

FROM Person.Person P INNER JOIN Person.PersonPhone H

ON P.BusinessEntityID = H.BusinessEntityID

ORDER BY LastName, FirstName, P.BusinessEntityID;

En este caso el operador INNER JOIN relaciona dos tablas -Person y PersonPhone- (cada una de estas tablas está renombrada para facilitar su referencia en la proyección y correlación). En la cláusula ON se especifican las dos columnas a comparar:

ON P.BusinessEntityID = H.BusinessEntityID

El resultado se ordena por apellido, primer nombre, y el identificador de la persona.

En Microsoft SQL Server Management Studio se ejecuta el código anterior y se obtienen los siguientes registros (versión compacta con 25 registros):

Figura 1. Correlación Person y PersonPhone.

7. Conclusiones

Con el operador INNER JOIN de T-SQL se correlacionan dos tablas a partir de la relación de igualdad entre dos columnas de cada tabla. El ejemplo de la sección 6 presentó cómo obtener el conjunto de personas que poseen por lo menos una línea telefónica, además de los números asociados a cada una. Este tipo de operación facilita responder a requerimientos de negocio sobre los tipos de relaciones que mantienen los tipos de datos de un dominio de problema.

La próxima receta T-SQL enseña cómo diseñar una consulta sobre una relación muchos-a-muchos.

8. Literatura & Enlaces

Brimhall, J., Dye, D., Gennick, J., Roberts, A., Sheffield, W. (2012). SQL Server 2012 T-SQL Recipes - A Problem-Solucion Approach. United States: Apress.
Using Joins (2016, abril 7). Recuperado desde: https://msdn.microsoft.com/en-us/library/ms191472.aspx

V

LINQ Recipe No. 1-3: How to Use the Various Types of Functions

Contents

1. Introduction
2. Keywords
3. Problem
4. Solution
5. Discussion
5.1 Generator functions
5.2 Statistical functions
5.3 Projector functions
5.4 Filter functions
6. Practice: Types of Functions - Examples
7. Conclusions
8. Literature & Links

1. Introduction

In this new LINQ recipe many new concepts about the different types of functions will be presented. We will study and practice how to use the kinds functions like: generator, statistical, projector, and filter. As we will see, these kinds of functions will allow us to manipulate data in more broadly way than the basic ones (those presented in recipes 1-1 and 1-2). In the practice section a series of examples will be explained to reinforce the comprehension for further recipes of this interesting topic: functional programming with LINQ in Microsoft .NET applications.

2. Keywords

• .NET
• Data
• Generator
• Filter
• Function
• LINQ
• Microsoft
• Projector

3. Problem

The programmer needs to learn which kinds of functions exist in functional programming and how they work to manipulate data in a more sophisticated way.

4. Solution

In functional programming there exist up to four categories for functions:

• Generators
• Statistical
• Projectors
• Filters

5. Discussion

The .NET Framework offers to the programmer, in the functional programming context, four types of functions.

illustration 1. Types of Functions (Mukherjee, 2014).

5.1 Generator functions

This kind of function lets the programmer to generate values out of nothing (Mukherjee, 2014). They can be represented using this equation:

() => T[]

Where T represents the output data type for the function. In the general sense, this type of function could be viewed like a method without parameters. The .NET Framework comes with many built-in generator functions; among them we have:

• Enumerable.Range(): generates a sequence of integral numbers between an specified range. ("Enumerable.Range Method", 2016).

5.2 Statistical functions

It's possible to generate statistics from a collection of elements. This is done by using the built-in statistical functions

• Any(): this function determines whether one or more elements satisfy some condition. Its return data type is bool. ("Enumerable.Any(TSource) Method", 2016)
• Count():  this function function returns the number of elements in a collection. ("Enumerable.Count(TSource)", 2016)
• Single(): this returns a single (one) element from a collection. ("Enumerable.Single (Method)", 2016)
• Sum(): calculates the addition of a collection of numerical elements. ("Enumerable.Sum (Method)", 2016)

Many of the above methods has multiple overloaded versions suited for different requirements.

On the other hand, the general syntax is

T[] => Boolean

T[] => Number

T[] corresponds to a collection of elements (more commonly integer values) and the return type is an primitive type like Boolean or Number.

5.3 Projector functions

The projector functions is suitable to process -project- a collection elements and return a collection of elements; i.e.:

T[] => U[]

For example, if we have a collection with city names and if we want to create -project- a collection with number of letters for each city name, then we must use a projector function to perform this process. The general equation for this example is 

String[] => Integer[]

Some of the available functions are: 

• Select(): projects each collection element from one representation to a new one. ("Enumerable.Select(TSource, TResult)", 2016)
• SelectMany(): project each collection element to an IEnumerable<T> data type. 

5.4 Filter functions

With these kind of functions the programmer can filter out the elements of a specified collection. Examples of these functions can be: 

• First(): 
• Last(): 
• Where(): 

According to Mukjerhee (2014) a filter function can be represented using either of these two equations:

• T[] => U[]: the filter function returns a list of elements (a collection).
• T[] => T: this function returns a single element according to condition or predicate.

6. Practice: Types of functions - Examples

Now we can proceed to elaborate some code example to reinforce our comprehension about the different kinds of functions.

Archivo C# TypeFunctionsExamples.cs [alternative link][alternative link]:

In line 14 we generate five integers -from 1 to 5-. With the line 24 we enlist 5 Microsoft products, then with the functional method Count we count the number of elements in the sequence: 5.

Now, we proceed with the use of projector functions. In particular, in the line 31, numbers from 1 to 5 are cubed. Finally with the code in the line 41 we select the first element from the string array msProducts.

Code compilation:

csc /t:exe TypeFunctionsExamples.cs

Assembly execution:

.\TypeFunctionsExamples.exe

Online assembly execution (ideone.com): http://ideone.com/RJpfw5

Local assembly execution:

Illustration 2. Assembly TypeFunctionsExamples.exe execution.

7. Conclusions

We have learned to distinguish the different kinds of functions: generators, statistical, projector, and filters. As we have seen all of these functions can be glued together to manipulate or transform data from different sources. In the example code presented, we have got a first sight to the functional programming methods available in the .NET Framework; in future recipes or articles we will go deeper.

In the next recipe we are going to understand the benefits of functional programming.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Enumerable.Range Method (System.Linq) (2016, March 4). Retrieved from: https://msdn.microsoft.com/en-us/library/system.linq.enumerable.range(v=vs.100).aspx
Enumerable.Any(TSource) (Method) (IEnumerable(TSource), Func(TSource, Boolean)) (System.Linq) (2016, March 5). Retrieved from: https://msdn.microsoft.com/library/bb534972(v=vs.100).aspx
Enumerable.Count(TSource) (Method) (IEnumerable(TSource)) (System.Linq) (2016, March 5). Retrieved from: https://msdn.microsoft.com/library/bb338038(v=vs.100).aspx
Enumerable.Single (Method) (System.Linq) (2016, March 5). Retrieved from: https://msdn.microsoft.com/es-es/library/system.linq.enumerable.single(v=vs.110).aspx
Enumerable.Sum Method (System.Linq) (2016, March 5). Retrieved from: https://msdn.microsoft.com/en-us/library/system.linq.enumerable.sum(v=vs.110).aspx
Enumerable.Select(TSource, TResult) Method (IEnumerable(TSource), Func(TSource, TResult)) (System.Linq) (2016, March 5). Retrieved from: https://msdn.microsoft.com/library/bb548891(v=vs.100).aspx
Enumerable.SelectMany(TSource, TResult) Method (IEnumerable(TSource), Func(TSource, IEnumerable(TResult))) (System.Linq) (2016, March 5). Retrieved from: https://msdn.microsoft.com/en-us/library/bb534336(v=vs.110).aspx

V