Skip to main content
1 de 4

El problema de tu implementación es que estás concatenando cada dígito al final de la lista en cada iteración. El operador ++ tiene un coste lineal respecto al número de elementos de la primera lista. Por tanto, si el número binario resultante tiene n dígitos, tu implementación hace (n-1) + (n-2) + (n-3) + ... + (n-n) iteraciones para construir la lista final, cuya progresión es igual a (n-1)*n/2, que resulta ser un orden de complejidad cuadrático respecto al número de dígitos del número binario.

Lo más común es construir la lista al revés (encabezando los elementos con :), y darle la vuelta al final en una única iteración. El operador : es el constructor de listas, que toma un elemento x y una lista xs y devuelve (en tiempo constante) la lista x:xs con cabeza x y cola xs.

toBin, auxBin :: Int -> [Int]
toBin 0 = [0]
toBin n = reverse (auxBin n)

auxBin 0 = []
auxBin n = n `mod` 2 : auxBin (n `div` 2)

Para contar el número de 1 de la lista resultante, puedes filtrar los elementos iguales a 1 con la función filter, y luego calcular la longitud con la función length:

ghci> filter (==1) [1,0,0,1,1]
[1,1,1]
ghci> length (filter (==1) [1,0,0,1,1])
3

Combinándolo con toBin en una función:

countOnes :: Int -> Int
countOnes = length . (filter (==1)) . toBin