Estoy luchando con Haskell, y la idea de usar la recursividad para iterar sobre las cosas.¿Cómo se traduciría este fragmento a Haskell?
Por ejemplo, ¿cómo
// this might seem silly but I need to do it
list1 = empty list
list2 = list of numbers
for i from 0 to N // N being a positive integer
for each number in list2
if number == i, add to list1
traducirse en el 'paradigma funcional'? Cualquier orientación sería apreciada.
ir paso a paso:
list2 = list of numbers
Vamos a tomar esto como un hecho, por lo list2 todavía es sólo una lista de números.
for i from 0 to N // N being a positive integer
La forma correcta de hacer esto en Haskell es por lo general con una lista. La pereza significa que los valores se computarán solo cuando se usen, por lo que recorrer una lista de 0 a N termina siendo lo mismo que el bucle que tienes aquí. Entonces, solo [0..n] hará el truco; solo tenemos que descubrir qué hacer con eso.
for each number in list2
Dada "para cada" se puede deducir que tendremos que recorrer la totalidad de list2 aquí; lo que hacemos con él, aún no lo sabemos.
if number == i, add to list1
Estamos construyendo list1 a medida que avanzamos, por lo que idealmente queremos que ese sea el resultado final de la expresión. Eso también significa que en cada paso recursivo, queremos que el resultado sea el list1 que tenemos "hasta ahora". Para hacer eso, necesitaremos asegurarnos de pasar el resultado de cada paso a medida que avanzamos.
Por lo tanto, ponerse manos a la carne de ella:
La función filter encuentran todos los elementos de una lista coinciden con alguna predicado; Usaremos filter (== i) list2 aquí para encontrar lo que buscamos, luego lo agregaremos al resultado del paso anterior. Así que cada paso se verá así:
step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2
que maneja el lazo interno. Retrocediendo, necesitamos ejecutar esto para cada valor i de la lista [0..n], con el valor list1 pasando en cada paso.Esto es exactamente lo que se pliegan para funciones son, y en este caso step es exactamente lo que necesitamos para un pliegue izquierda:
list2 :: (Num a) => [a]
list2 = -- whatever goes here...
step :: (Num a) => [a] -> a -> [a]
step list1 i = list1 ++ filter (== i) list2
list1 :: (Num a) => a -> [a]
list1 n = foldl step [] [0..n]
Si usted se pregunta dónde está la recursividad, tanto filter y foldl lo están haciendo por nosotros . Como regla general, generalmente es mejor evitar la recursión directa cuando hay funciones de nivel superior para hacerlo por usted.
Dicho esto, el algoritmo aquí es tonta de múltiples maneras, pero yo no quería entrar en eso, ya que parecía que iba a distraer la atención de su pregunta real más de lo que sería de ayuda.
Lo sentimos, pero no puedo dejar de utilizar un algoritmo mejor ...
let goodNumber n = (0 <= n && n < N)
let list1 = sort (filter goodNumber list2)
Editar: En retrospectiva, esto es un poco de exageración, ya que la OP estaba tratando de poner en práctica una ordenar algo en primer lugar.
let list1 = sort [a | a<-list2, a>=0, a<=N]
a<-list2 recoge cada número de lista2 a>=0, a<=N de verificación si el número elegido cumple con todas estas condiciones si se cumplen las condiciones, una se pone en una nueva lista Una vez que todos los elementos de lista2 han sido por lo tanto comprobado y poner en una nueva lista, hacemos una especie en este La lista resultante está asignada a list1
¿Por qué no utilizar 'concatMap' en lugar de plegar sobre un paso de concatenación explícito? – bdonlan
Tenga en cuenta que en este caso, puede usar la comprensión de la lista: [number | i <- [1..N], number <-list2, i == number] que es la traducción directa de su pseudo-código. – ysdx
Gracias por una gran respuesta. Me doy cuenta de que el fragmento que publiqué es extraño ... Rabí drásticamente cualquier significado fuera de él. Es parte de un ejercicio de tipo radical que estoy haciendo. –