Prefijo con suma acotada

PorJosé A. Alonso 7-febrero-201714-febrero-2017

Definir la función

   prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

1	prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

tal que (prefijoAcotado x ys) es el mayor prefijo de ys cuya suma es menor que x. Por ejemplo,

   prefijoAcotado 10 [3,2,5,7]  ==  [3,2]
   prefijoAcotado 10 [1..]      ==  [1,2,3]

1 2	prefijoAcotado 10 [3,2,5,7] == [3,2] prefijoAcotado 10 [1..] == [1,2,3]

Soluciones

-- 1ª definición (por recursión):
prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x [] = []
prefijoAcotado x (y:ys)
  | y < x     = y : prefijoAcotado (x-y) ys
  | otherwise = []

-- 2ª definición (con scanl1 y takeWhile):
prefijoAcotado2 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado2 x ys = map fst conSumasAcotadas
  where 
    sumas            = scanl1 (+) ys 
    conSumas         = zip ys sumas
    conSumasAcotadas = takeWhile (\(a,b) -> b < x) conSumas

-- 3ª definición (con (.)):
prefijoAcotado3 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado3 x ys = map fst conSumasAcotadas
  where 
    sumas            = scanl1 (+) ys 
    conSumas         = zip ys sumas
    conSumasAcotadas = takeWhile ((<x) . snd) conSumas

-- 4ª definición:
prefijoAcotado4 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado4 x ys = 
    map fst (takeWhile ((<x) . snd) (zip ys (scanl1 (+) ys)))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

-- 1ª definición (por recursión):

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado x [] = []

prefijoAcotado x (y:ys)

| y < x = y : prefijoAcotado (x-y) ys

| otherwise = []

-- 2ª definición (con scanl1 y takeWhile):

prefijoAcotado2 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado2 x ys = map fst conSumasAcotadas

where

sumas = scanl1 (+) ys

conSumas = zip ys sumas

conSumasAcotadas = takeWhile (\(a,b) -> b < x) conSumas

-- 3ª definición (con (.)):

prefijoAcotado3 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado3 x ys = map fst conSumasAcotadas

where

sumas = scanl1 (+) ys

conSumas = zip ys sumas

conSumasAcotadas = takeWhile ((<x) . snd) conSumas

-- 4ª definición:

prefijoAcotado4 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado4 x ys =

map fst (takeWhile ((<x) . snd) (zip ys (scanl1 (+) ys)))

12 Comentarios

prefijoAcotado :: (Num a,Ord a) => a -> [a] -> [a]
prefijoAcotado n xs = aux n xs []
  where aux _ []     _  = []
        aux n (x:xs) ys | x + sum ys < n = aux n xs (x:ys)
                        | otherwise      = reverse ys

1

2

3

4

5

prefijoAcotado :: (Num a,Ord a) => a -> [a] -> [a]

prefijoAcotado n xs = aux n xs []

where aux _ [] _ = []

aux n (x:xs) ys | x + sum ys < n = aux n xs (x:ys)

| otherwise = reverse ys

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado a xs = aux 0 a xs
  where aux s a (x:xs) | s+x >= a  = []
                       | otherwise = x : aux (s+x) a xs

1

2

3

4

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado a xs = aux 0 a xs

where aux s a (x:xs) | s+x >= a = []

| otherwise = x : aux (s+x) a xs

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado = aux []
  where
    aux ys n (x:xs)
     | sum ys + x < n = aux (ys++[x]) n xs
     | otherwise      = ys

1

2

3

4

5

6

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado = aux []

where

aux ys n (x:xs)

| sum ys + x < n = aux (ys++[x]) n xs

| otherwise = ys

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado _ [] = []
prefijoAcotado 0 _  = []
prefijoAcotado n (x:xs)
  | x >= n    = []
  | otherwise = x : prefijoAcotado (n-x) xs

1

2

3

4

5

6

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado _ [] = []

prefijoAcotado 0 _ = []

prefijoAcotado n (x:xs)

| x >= n = []

| otherwise = x : prefijoAcotado (n-x) xs

monlagare dice:

7-febrero-2017 a las 16:59

Sólo para listas finitas

Haskell

import Data.List prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a] prefijoAcotado x ys = last [zs | zs <- inits ys, sum zs < x]

1
2
3
4

import Data.List

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x ys = last [zs | zs <- inits ys, sum zs < x]

Responder

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x ys = reverse (auxP x (scanl1 (+) ys) ys [])
  where auxP x (z:zs) (y:ys) ts | z >= x    = ts
                                | otherwise = auxP x zs ys (y:ts)
        auxP _ _ [] ts = ts

1

2

3

4

5

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado x ys = reverse (auxP x (scanl1 (+) ys) ys [])

where auxP x (z:zs) (y:ys) ts | z >= x = ts

| otherwise = auxP x zs ys (y:ts)

auxP _ _ [] ts = ts

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x [] = []
prefijoAcotado x ys = aux x ys 0
  where aux x (y:ys) n | y + n < x = y : aux x ys (y+n)
                       | otherwise = []

1

2

3

4

5

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado x [] = []

prefijoAcotado x ys = aux x ys 0

where aux x (y:ys) n | y + n < x = y : aux x ys (y+n)

| otherwise = []

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado k xs = reverse $ aux k xs []
 where aux k [] ys = ys
       aux k (x:xs) ys | sum (x:ys) < k = aux k xs (x:ys)
                       | otherwise      = ys

1

2

3

4

5

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado k xs = reverse $ aux k xs []

where aux k [] ys = ys

aux k (x:xs) ys | sum (x:ys) < k = aux k xs (x:ys)

| otherwise = ys

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado n [] = []
prefijoAcotado n (x:xs)
  | n <= x    = []
  | otherwise = x : prefijoAcotado (n-x) xs

1

2

3

4

5

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado n [] = []

prefijoAcotado n (x:xs)

| n <= x = []

| otherwise = x : prefijoAcotado (n-x) xs

Chema Cortés dice:

8-febrero-2017 a las 00:12

Haskell

import Data.List prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a] prefijoAcotado x = last . takeWhile ((x>).sum) . inits

1
2
3
4

import Data.List

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x = last . takeWhile ((x>).sum) . inits

Responder

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x [] = []
prefijoAcotado x (n:xs)
  | x < n     = []
  | otherwise = take (length ps) (n:xs)
  where ps = takeWhile (<x) (scanl1 (+) (n:xs))

1

2

3

4

5

6

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado x [] = []

prefijoAcotado x (n:xs)

| x < n = []

| otherwise = take (length ps) (n:xs)

where ps = takeWhile (<x) (scanl1 (+) (n:xs))

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x ys = reverse (aux x [] ys)

aux :: (Num a, Ord a) => a -> [a] -> [a] -> [a]
aux h zs []     = zs
aux h zs (a:as) | sum zs < h  =  aux h (a:zs) as
                | otherwise   =  tail zs

1

2

3

4

5

6

7

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado x ys = reverse (aux x [] ys)

aux :: (Num a, Ord a) => a -> [a] -> [a] -> [a]

aux h zs [] = zs

aux h zs (a:as) | sum zs < h = aux h (a:zs) as

| otherwise = tail zs

Leave a Reply to antmorper3Cancel reply