Empecemos con nuestro ejercicio estrella: recomendar amigos en una red social. En el día anterior especificamos el problema a alto nivel, es decir, distinguimos sus diferentes partes pero no entramos en detalle sobre cómo se podrían implementar cada una de estas partes. Repasemos qué era lo que tenía que hacer el programa, y añadamos de paso un par de funcionalidades más :

1. obtener la lista de todos los amigos de los amigos de la persona a quien queremos recomendar nuevos amigos (llamémosle p). Para eso necesitaremos la función losAmigosDeMisAmigos :: [Int] → [(Int,String,[Int])] → [Int], que se puede armar usando la función auxiliar listaDeAmigos :: Int → [(Int,String,[Int])] → [Int].
2. quedarnos solamente con los amigos que son amigos por lo menos de dos amigos de p, es decir, descartar los que son amigos solamente de uno de los amigos de p.
3. eliminar duplicados de esa lista. Fíjense que este paso no podemos hacerlo antes porque si no no podríamos detectar cuáles son los amigos que son amigos por lo menos de dos amigos de p.
4. descartar de esa lista todos los que ya son amigos de p, es decir, que ya están en la lista de amigos de p. Para eso necesitaremos la función filtrarNoEstanEnLista :: [Int] → [Int] → [Int].
5. descartar de esa lista a p.
6. asignar el nombre a cada una de las personas que recomendamos, de las cuales de momento sólo conocemos su número identificador.

La función principal recomendarNuevosAmigos se puede definir ahora como una combinación de todas estas funciones auxiliares, por ejemplo, de la siguiente manera:

recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]
recomendarNuevosAmigos (id,n,misamigos) directorio = 
  asignarNombre directorio (
      filter (noEs id) ( 
   	  filtrarNoEstanEnLista misamigos ( 
	     eliminarDuplicados ( 
	        filtrarExiste2 ( 
		   losAmigosDeMisAmigos misamigos directorio 
                ) 
             ) 
         ) 
      )
   )

Fíjense que si escribimos la función indentada, podremos comentar las partes que todavía no hayamos desarrollado y probar solamente las que ya hemos desarrollado, pero teniendo en todo momento a la vista la estructura de alto nivel del programa. Fíjense que en algunos casos, si comentamos algunas partes de la función, puede cambiar la signatura de tipos.

Ahora lo que tenemos que hacer es desarrollar cada una de las partes que hemos especificado, por separado. Vamos a ver que muchas de estas partes son filtros, pero con algunas diferencias con los filtros estándares, lo que hace difícil que podamos usar la generalización filter.

En primer lugar, vamos a desarrollar la subfunción (o subrutina) para crear una lista con todas las personas que son amigas de mis amigos. Como está especificado en la definición de alto nivel de la función principal, esta subfunción va a trabajar con la lista de los identificadores de mis amigos y el directorio de todas las personas que hay en la red social, y va a devolver una lista con los identificadores de los amigos de mis amigos. La signatura de tipos sería como sigue:

losAmigosDeMisAmigos :: [Int] -> [(Int,String,[Int])] -> [Int]

Y la función se podría definir como sigue:

losAmigosDeMisAmigos [] _ = []
losAmigosDeMisAmigos (a:amigos) directorio = ( listaAmigos a directorio ) ++ losAmigosDeMisAmigos amigos directorio

Fíjense que estamos usando una función auxiliar, es decir, otra subrutina: listaAmigos. Esta función encuentra la lista de los amigos de una persona en el directorio, por lo tanto, toma como argumentos el identificador de la persona y el directorio, y devuelve una lista con los identificadores de los amigos de esta persona. Se podría definir como sigue:

listaAmigos :: Int -> [(Int,String,[Int])] -> [Int]
listaAmigos _ [] = []
listaAmigos a ((id,n,amigos):xs) | id == a   = amigos
                                 | otherwise = listaAmigos a xs

Fíjense que esta función tiene una estructura semejante a un filtro pero con dos diferencias: el predicado que se evalúa trabaja con subpartes de la cabeza de la lista. Ademá, en el caso positivo se corta la recursividad, ya que una vez encontrada la lista de amigos de la persona no necesitamos seguir buscando.

Ahora que ya tenemos esto, podemos probar una parte de la función principal, comentando el resto y cambiando la signatura de tipos:

--recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]
recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [Int]
recomendarNuevosAmigos (id,n,misamigos) directorio = 
--  asignarNombre directorio (
--      filter (noEs id) ( 
--   	  filtrarNoEstanEnLista misamigos ( 
--	     eliminarDuplicados ( 
--	        filtrarExiste2 ( 
		   losAmigosDeMisAmigos misamigos directorio 
--                ) 
--             ) 
--         ) 
--      )
--   )

Ahora esta función nos devolverá la lista de todos los amigos de mis amigos. Por ejemplo:

Main> recomendarNuevosAmigos (2,"b",[1,3]) [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
[2,3,4,1,2,4]

También podríamos comentar toda la función principal, y probar solamente las subrutinas, para comprobar que hacen lo que esperamos que hagan:

Main> listaAmigos 3 [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
[1,2,4]

Main> losAmigosDeMisAmigos [3,4] [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
[1,2,4,2,3]

Sigamos ahora con otra parte de la función principal. Vamos a definir la subrutina que nos permite quedarnos únicamente con las personas que aparecen por lo menos dos veces en la lista de amigos de mis amigos. Como definimos en la función principal, esta función toma el directorio y la lista de amigos de mis amigos resultante de la subrutina que recién acabamos de definir, y nos devuelve una lista que contiene solamente los identificadores de las personas que ocurren por lo menos dos veces en la lista. Por lo tanto, es muy parecido a un filtro, pero con una diferencia: el predicado que se evalúa toma dos argumentos. Por esta razón no podemos usar la generalización filter.

filtrarExiste2 :: [Int] -> [Int]
filtrarExiste2 [] = []
filtrarExiste2 (x:xs) | existe2 x (x:xs) = x : filtrarExiste2 xs
                      | otherwise        =     filtrarExiste2 xs

Vemos que para definir filtrarExiste2 necesitamos definir el predicado existe2, que a su vez necesita del predicado existe1, tal como los definimos acá:

existe2 :: Int -> [Int] -> Bool
existe2 a [] = False
existe2 a (x:xs) | a == x     = existe1 a xs
                         | otherwise = existe2 a xs

existe1 :: Int -> [Int] -> Bool
existe1 a xs = elem a xs

Ahora que ya tenemos definida esta parte de la función, vamos a probarla. Podemos descomentar la parte de la función principal que usa esta subfunción:

--recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]
recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [Int]
recomendarNuevosAmigos (id,n,misamigos) directorio = 
--  asignarNombre directorio (
--      filter (noEs id) ( 
--   	  filtrarNoEstanEnLista misamigos ( 
--	     eliminarDuplicados ( 
	        filtrarExiste2 ( 
		   losAmigosDeMisAmigos misamigos directorio 
                ) 
--             ) 
--         ) 
--      )
--   )

Y probamos la función principal:

recomendarNuevosAmigos (2,"b",[1,3]) [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
[2,4]

También podemos probar las subfuncines por separado:

Main> existe1 3 [1,2,3]
True
Main> existe2 3 [1,2,3]
False
Main> existe2 3 [1,2,3,3]
True
Main> filtrarExiste2 [1,2,3,3]
[3]

Seguimos desarrollando otra subfunción: la que elimina los elementos duplicados. También se trata de un filtro, ya que solamente se queda con un elemento si hay más de uno igual, pero como el predicado que se aplica es complejo, tampoco podemos usar la generalización filter. Veamos cómo sería:

eliminarDuplicados :: [Int] -> [Int]
eliminarDuplicados [] = []
eliminarDuplicados (x:xs) | elem x xs =     eliminarDuplicados xs
                          | otherwise = x : eliminarDuplicados xs

Probamos la subfunción y vemos que funciona bien:

Main> eliminarDuplicados [1,2,3,1,3,4,5,5]
[2,1,3,4,5]

La siguiente subfunción que queremos desarrollar es la que filtra las personas de la lista de posibles recomendaciones que ya están en la lista de mis propios amigos. De vuelta se trata de un filtro algo más complejo:

filtrarNoEstanEnLista :: [Int] -> [Int] -> [Int]
filtrarNoEstanEnLista [] xs = xs
filtrarNoEstanEnLista xs [] = []
filtrarNoEstanEnLista (x:xs) ys = filtrarNoEstanEnLista xs (filter (/=x) ys)

Ahora queremos filtrar a una persona especial: yo mismo! esto podríamos hacerlo incorporándome a la lista de mis propios amigos, o también mediante un filtro simple, esta vez sí! Lo vemos así en la función principal: filter (noEs id) LISTARECOMENDADOS. Sólo tenemos que definir el predicado noEs:

noEs :: Int -> Int -> Bool
noEs a b = a /= b

Ahora ya tenemos una lista con los identificadores de las personas que queremos recomendar como posibles amigos a alguien. Se trata de personas que son amigos de por lo menos dos de sus amigos pero de las cuales todavía no es amigo él mismo.

Finalmente, sólo nos queda una cuestión estética. Hasta el momento hemos estado trabajando con los identificadores de las personas, pero la información final que vamos a querer mostrarle a nuestro usuario será no solamente el identificador, sino también el nombre, porque resulta mucho más agradable para una persona. Los identificadores son útiles para las máquinas, pero no para las personas. Por esta razón vamos a querer asociar a cada uno de los identificadores de las personas que queremos recomendar a su nombre. Para ello vamos a consultar la información del directorio una vez más, junto con la lista de identificadores de personas recomendadas, de la siguiente forma:

asignarNombre :: [(Int,String,[Int])] -> [Int] -> [(String,Int)]
asignarNombre _ [] = []
asignarNombre directorio (x:xs) = ( (encuentraNombre x directorio), x ) : asignarNombre  directorio xs

La función auxiliar encuentraNombre se definiría así:

encuentraNombre :: Int -> [(Int,String,[Int])] -> String
encuentraNombre x [] = "el usario no se encuentra en el directorio"
encuentraNombre x ((id,nombre,amigos):xs) | id == x   = nombre
                                          | otherwise = encuentraNombre x xs

Ahora sí, podemos cambiar la signatura de tipos de la función principal según la habíamos pensado inicialmente:

recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]

Descomentar todas las líneas y probarla:

recomendarNuevosAmigos (2,"b",[1,3]) [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
[("d",4)]

Funciona como queríamos!

Ahora, cómo sería este mismo problema en prolog? Vamos a tratar de aplicar la misma aproximación: primero vemos el problema a alto nivel, nos damos cuenta de cuáles son las diferentes partes del problema y cómo están relacionadas entre ellas, y después pasamos a desarrollar cada una de estas partes independientemente.