YES
Input TRS:
      1: g(A()) -> A()
      2: g(B()) -> A()
      3: g(B()) -> B()
      4: g(C()) -> A()
      5: g(C()) -> B()
      6: g(C()) -> C()
      7: foldf(x,nil()) -> x
      8: foldf(x,cons(y,z)) -> f(foldf(x,z),y)
      9: f(t,x) -> f'(t,g(x))
      10: f'(triple(a,b,c),C()) -> triple(a,b,cons(C(),c))
      11: f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
      12: f'(triple(a,b,c),A()) -> f''(foldf(triple(cons(A(),a),nil(),c),b))
      13: f''(triple(a,b,c)) -> foldf(triple(a,b,nil()),c)
Number of strict rules: 13
Direct POLO(bPol) ... removes: 4 5 11 2
      triple	w: x1 + x2 + x3 + 13214
      C 	w: 24775
      f 	w: x1 + x2 + 14098
      B 	w: 24774
      A 	w: 24773
      nil	w: 0
      f'	w: x1 + x2 + 14098
      cons	w: x1 + x2 + 14098
      foldf	w: x1 + x2
      g 	w: x1
      f''	w: x1
Number of strict rules: 9
Direct POLO(bPol) ... removes: 7 12 13
      triple	w: x1 + 2 * x2 + 2 * x3 + 1
      C 	w: 23975
      f 	w: x1 + 2 * x2 + 21614
      B 	w: 5662
      A 	w: 5662
      nil	w: 1911
      f'	w: x1 + 2 * x2 + 21614
      cons	w: x1 + x2 + 10807
      foldf	w: x1 + 2 * x2 + 1
      g 	w: x1
      f''	w: x1 + 12645
Number of strict rules: 6
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #f(t,x) -> #f'(t,g(x))
     #2: #f(t,x) -> #g(x)
     #3: #foldf(x,cons(y,z)) -> #f(foldf(x,z),y)
     #4: #foldf(x,cons(y,z)) -> #foldf(x,z)
Number of SCCs: 1, DPs: 1
  SCC { #4 }
POLO(Sum)... succeeded.
      #f'	w: 0
      triple	w: 0
      #foldf	w: x2
      C 	w: 0
      f 	w: 0
      B 	w: 0
      A 	w: 0
      nil	w: 0
      #f 	w: 0
      #g 	w: 0
      f'	w: 0
      cons	w: x2 + 1
      foldf	w: 0
      g 	w: 0
      f''	w: 0
    USABLE RULES: { }
    Removed DPs: #4
Number of SCCs: 0, DPs: 0